[백준] 14226번 : 이모티콘 - JAVA [자바]

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

---

bfs 알고리즘 문제이다.

문제에서 주어진 3가지 조건에 따라 상태를 다르게 만들어 큐에 삽입하여 bfs 알고리즘을 돌린다.

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

이모티콘의 갯수가 S가 되면 반복문을 종료하고 정답을 출력한다.

먼저 현재 화면의 이모티콘 갯수, 클립보드에 있는 이모티콘의 갯수, 걸린 시간을 저장하는 클래스를 사용한다.

public static class Emoticon {
	int clipboard;
	int display;
    int time;

	public Emoticon(int clipboard, int display, int time) {
    	this.clipboard = clipboard;
        this.display = display;
        this.time = time;
	}
}

먼저 현재 화면에 이모티콘의 갯수가 1, 클립보드에는 0, 시간은 0 인 상태로 출발한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 덮어쓴다.
   -> 클립보드에 현재 이모티콘의 갯수를 넣고 시간을 +1 한 상태를 큐에 삽입한다.
   -> queue.add(new Emoticon(start.display, start.display, start.time + 1))

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
   -> 클립보드에 있는 이모티콘 갯수를 현재 화면의 이모티콘 갯수에 더한 것을 화면의 이모티콘의 갯수로 넣은 상태를 큐에 삽입한다.
   -> queue.add(new Emoticon(start.display + start.clipboard, start.clipboard, start.time + 1))

3. 화면에 있는 이모티콘 중 하나를 삭제한다.
   -> 현재 화면에 있는 이모티콘의 갯수 -1 한 갯수의 상태를 큐에 삽입한다.
   -> queue.add(new Emoticon(start.display - 1, start.display, start.time + 1))

위의 방법대로 큐에 삽입하며 bfs 알고리즘으로 탐색하다가 화면의 이모티콘의 갯수가 S 가 되면 반복문을 탈출하고 정답을 출력한다.

하지만 위의 방법대로 하면 메모리 초과가 발생한다.
그 이유를 알아보기 위해 먼저 처음 시작하는 상태일 때부터 보자.

2번 조건에 따라 화면의 이모티콘의 갯수(1)에 현재 클립보드에 있는 이모티콘의 갯수(0)을 붙이면 시간만 늘어나고 현재 이모티콘의 갯수와 클립보드의 갯수는 변함이 없다. 즉, 가장 빠른 방법이 아닌 다른 방법이 계속 큐에 들어가서 의미 없는 반복만 생기는 것이다.

이를 해결하기 위해 visited[2001][2001] 배열을 사용했다.
문제의 조건에 따라 S <= 2000 이기 때문에 범위를 저렇게 잡았고 2차원 배열을 사용한 이유는 현재 [이모티콘 갯수][클립보드의 갯수] 이다.

1. 1 번 조건 은 visited[start.display][start.display] 를 살펴본다.
   -> 현재 이모티콘의 갯수를 클립보드에 복사한 상태가 이미 있는지 보는 것이다.

2. 2 번 조건 은 !visited[start.display + start.clipboard][start.clipboard] 를 살펴본다.
   -> 현재 클립보드의 갯수를 현재 화면의 이모티콘의 갯수에 더한 상태가 이미 있는지 보는 것이다.
   -> 또한, 현재 클립보드의 갯수가 0 이면 의미 없는 행동이므로 패스한다.
   -> 그리고 붙여넣었을 때 문제의 조건인 2000을 넘어가서 visited 배열의 index를 초과하면 안되므로 조건에 추가한다.

3. 3 번 조건 은 visited[start.display - 1][start.clipboard] 를 살펴본다.
   -> 현재 이모티콘의 갯수에서 -1 한 상태가 이미 있는지 보는 것이다.
   -> 또한, 현재 이모티콘의 갯수가 0이면 -1을 할 수 없으므로 패스한다.

위의 조건을 추가하고 bfs 알고리즘을 돌다가 이모티콘의 갯수가 S 인 상태의 time 을 출력하면 된다.

---

public class bj14226 {

    public static int S;
    public static boolean[][] visited = new boolean[2001][2001];
    public static Queue<Emoticon> queue = new LinkedList<>();
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        S = Integer.parseInt(br.readLine());

        bfs(new Emoticon(0, 1, 0));

        bw.write(sb + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(Emoticon start) {
        queue.add(start);

        while (!queue.isEmpty()) {
            start = queue.poll();
            if (start.display == S) {
                sb.append(start.time);
                break;
            }
            // 1. 화면에 있는 이모티콘 갯수 클립보드에 덮어쓰기
            // 1개를 덮어쓰고 큐에 삽입 -> 또 1개를 덮어쓰고 큐에 삽입 : 반복
            if (!visited[start.display][start.display]) {
                visited[start.display][start.display] = true;
                queue.add(new Emoticon(start.display, start.display, start.time + 1));
            }
            // 2. 클립보드에서 불러와서 화면에 붙여넣기
            // 0개를 붙여 넣는건 의미없으며 시간만 늘어나므로 패스
            // 붙여넣었을 때 문제의 조건인 2000개를 넘어가면 안되므로 패스
            if (start.clipboard != 0 && start.display + start.clipboard <= 2000) {
                if (!visited[start.display + start.clipboard][start.clipboard]) {
                    visited[start.display + start.clipboard][start.clipboard] = true;
                    queue.add(new Emoticon(start.clipboard, start.display + start.clipboard, start.time + 1));
                }
            }
            // 3. 화면에 있는 이모티콘 1개 삭제
            // 화면에 이모티콘이 없으면 삭제할 수 없으므로
            if (start.display > 0) {
                // 삭제하여 만들어진 상태가 이미 있는 상태이면 더 오래 걸리는 방법이므로 패스
                if (!visited[start.display - 1][start.clipboard]) {
                    visited[start.display - 1][start.clipboard] = true;
                    queue.add(new Emoticon(start.clipboard, start.display - 1, start.time + 1));
                }
            }
        }
    }

    public static class Emoticon {
        int clipboard;
        int display;
        int time;

        public Emoticon(int clipboard, int display, int time) {
            this.clipboard = clipboard;
            this.display = display;
            this.time = time;
        }
    }

}