[JAVA] #14226 이모티콘

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

14226번: 이모티콘

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int S;
    static boolean[][] visited = new boolean[2001][2001]; // [화면][클립보드]

    public static class Node {
        int screen; // 화면에 있는 이모티콘 개수
        int cb; // 클립보드에 복사된 이모티콘 개수
        int time; // 현재 소요시간
        Node(int screen, int cb, int time) {
            this.screen = screen;
            this.cb = cb;
            this.time = time;
        }
    }

    public static void bfs(int n) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n, 0, 0));
        visited[n][0] = true;
        while(!queue.isEmpty()) {
            Node e = queue.poll();
            if(e.screen == S) {
                System.out.println(e.time);
                System.exit(0);
            }
            // 1. 클립보드에 현재 이모티콘 개수 저장
            queue.add(new Node(e.screen, e.screen, e.time + 1));

            // 2. 이모티콘 붙여넣기
            if(e.screen + e.cb <= 1000 && !visited[e.screen + e.cb][e.cb]) {
                queue.add(new Node(e.screen + e.cb, e.cb, e.time + 1));
                visited[e.screen + e.cb][e.cb] = true;
            }

            // 3. 화면에서 이모티콘 하나 삭제
            if(e.screen - 1 > 0 && !visited[e.screen - 1][e.cb]) {
                queue.add(new Node(e.screen - 1, e.cb, e.time + 1));
                visited[e.screen - 1][e.cb] = true;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        bfs(1);
    }
}

쉽게 접근했다가 큰코 다쳤다.

내 머리속으로는 암만 생각해도 도저히 이해가 안되서 다른 사람들의 코드를 참고했는데 그대로 따라 쳐봐도 왜 이차원 visited 배열을 사용하는지 직접 짜보고 나서도 이해가 잘 안되었다.

 

[처음 문제를 본 이후 내 접근]

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

1697번: 숨바꼭질

위 문제랑 거의 유사한 문제인 줄 알았다.

최단거리를 계산할 수 있는 BFS 알고리즘을 이용하면 특정 이모티콘이 출력되는 개수까지 이동하는 최소 시간을 얻어낼 수 있겠거니 하고 풀었다.

 

public class Main {

    static int S;
    static int[] board = new int[2001];
    static boolean[] visited = new boolean[2001];

    public static class Node {
        int idx;
        int cb;
        Node(int idx, int cb) {
            this.idx = idx;
            this.cb = cb;
        }
    }

    public static void func(int n) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n, 0));
        visited[n] = true;
        while(!queue.isEmpty()) {
           Node e = queue.poll();
           if(e.idx - 1 > 0 && !visited[e.idx - 1]) { // 1. 하나를 삭제하는 연산
               board[e.idx - 1] = board[e.idx] + 1;
               visited[e.idx - 1] = true;
               queue.add(new Node(e.idx - 1, e.cb)); // 클립보드 개수는 변화 X
           }
           if(e.idx + e.cb <= 1000 && !visited[e.idx + e.cb]) { // 2. 클립보드 붙여넣기 연산
               board[e.idx + e.cb] = board[e.idx] + 1;
               visited[e.idx + e.cb] = true;
               queue.add(new Node(e.idx + e.cb, e.cb)); // 클립보드 개수는 변화 X
           }
           if(e.idx * 2 <= 1000 && !visited[e.idx * 2]) { // 3. 클립보드 복사 후 붙여넣기 연산
               board[e.idx * 2] = board[e.idx] + 2;
               visited[e.idx * 2] = true;
               queue.add(new Node(e.idx * 2, e.idx)); // 클립보드 개수 변화
           }
           if(board[S] != 0) {
               System.out.println(board[S]);
               System.exit(0);
           }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        visited[0] = true;
        func(1);
    }
}

아는 문제가 나온 것 같아 싱글벙글 하면서 풀었다.

 

그런데 답이 틀렸다고 나왔다.

 

왜인지 도저히 이해가 되지 않았다.

그때부터 머리가 돌머리가 되고 속이 건빵 한봉지를 우유 없이 먹은듯이 답답해져왔다.

왜일까...??

 

BFS를 이용하면 최소시간을 이용해서 가는 케이스를 찾을 수 있지 않나?

종이에 10까지 적어놓고 직접 흐름을 따라가봐도 잘못된 부분이 없어보였다.

 

질문 게시판을 찾아본 결과,

"어떤 점에 더 늦게 도착해도, 클립보드에 저장된 이모티콘의 개수가 더 많다면 그게 더 빠를 수 있다"

는 점을 놓친 것 같다.

 

결국 위 방식의 코드는 클립보드에 저장된 이모티콘의 개수 각각의 경우를 모두 비교해보지 않는다.

 

이것이 핵심이었던 것 같다.

 

그래서!

 

클립보드에 저장된 이모티콘의 개수에 따른 경우의 수를 각각 체크해보기 위해서 이차원 visited 배열을 사용한 것이다.

(visited[화면 내 이모티콘 개수][클립보드에 저장된 이모티콘 개수])

 

 

참고) 그냥 visited 배열을 안쓰면 안되나?

클립보드에 현재 화면의 이모티콘을 복사하는 케이스에서 발생하는 문제가 있는데

 

현재 화면에 이모티콘 1개

클립보드에 이모티콘 1개

소요 시간 1초

 

인 상태라고 할때(1, 1, 1), 별도의 조건문으로 걸러주지를 않으면

(1, 1, 2), (1, 1, 3), (1, 1, 4)... 인 결과에 영향도 없으면서 쓸데없이 메모리와 시간만 잡아먹는 노드가 큐에 들어가게 된다

그래서 이차원 배열로 걸러줘야함

 

 

뭔가 찝찝한 해결이다

 

한 2주 뒤에 다시 풀어보면 또 못풀 것 같은데 

아직 실력이 한참 부족한 것 같다