[백준] 14226 이모티콘

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

2022-08-15

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main14226 {
    static class Emoticon {
        int val;
        int copy;
 
        public Emoticon(int val, int copy) {
            this.val = val;
            this.copy = copy;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        Queue<Emoticon> q = new LinkedList<>();
        q.add(new Emoticon(1, 0));
 
        int time = 0;
        boolean[][] vtd = new boolean[S*2+1][S*2+1];
        loop:while(!q.isEmpty()) {
            int size = q.size();
            while(size > 0) {
                Emoticon e = q.poll();
                if(e.val == S) break loop;
                if(!vtd[e.val][e.val]) {
                    q.add(new Emoticon(e.val, e.val)); // 1
                    vtd[e.val][e.val] = true;
                }
                if(e.val+e.copy <= S*2 && !vtd[e.val+e.copy][e.copy]) {
                    q.add(new Emoticon(e.val+e.copy, e.copy)); // 2
                    vtd[e.val+e.copy][e.copy] = true;
                }
                if(e.val-1 >= 2 && !vtd[e.val-1][e.copy]) {
                    q.add(new Emoticon(e.val-1, e.copy)); // 3
                    vtd[e.val-1][e.copy] = true;
                }
                size--;
            }
            time++;
        }
        System.out.println(time);
    }
}

#문제풀이

아래 연산들은 모두 1초 씩이어서 한 케이스 당 3개의 연산들을 한 번씩 다 적용 했다. 

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

조건 중 S가 2 <= S <= 1000 이므로, visited를 체크하는 배열은 S*2+1로 잡았다.