13913번 - 숨바꼭질4(bfs)

드디어 마지막 숨바꼭질 문제다.

문제:

수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1 또는 2*X의 위치로 이동할 수 있다.

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법을 구하시오.

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

풀이:

이전 숨바꼭질 문제들과 같이 bfs를 활용하여 푸는 문제이다.

수빈이가 현 위치에서 다음 위치로 갈때, 다음 위치에 현 위치에서 출발했다는 흔적을 남기고,
역순으로 출력해주면 문제가 풀릴 것이다.

이를 위한 코드는 아래와 같다.

static void bfs() {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(N);

    while (!queue.isEmpty()) {
        int num = queue.poll();
        if (num == K) {
            return;
        }
        if (num+1 < size && position[num+1] == -1) {
            queue.add(num+1);
            position[num+1] = num;
            time[num+1] = time[num] + 1;
        }
        if (num*2 < size && position[num*2] == -1) {
            queue.add(num*2);
            position[num*2] = num;
            time[num*2] = time[num] + 1;
        }
        if (num-1 >= 0 && position[num-1] == -1) {
            queue.add(num-1);
            position[num-1] = num;
            time[num-1] = time[num] + 1;
        }
    }
}

1. 해당 위치로 오기 위해, 어느 위치에서 출발했는지를 나타내는 position[] 배열과
   해당 위치로 오기 위한 최단 시간인 time[] 배열을 준비한다.
   position[] 배열은 모든 값을 -1로 초기화하고, time[]는 0이면 된다.
2. bfs 문제이므로 queue를 이용한다. 추가된 순서대로 꺼내 볼 수 있으니 bfs에 어울린다.
3. queue에 수빈이의 출발 위치인 N을 추가해준다.
4. queue에서 하나의 수(num)를 poll()한다.
   1.  num이 K면 메서드를 종료한다.
   2. num+1, num*2, num-1이 갈 수 있는 위치인지 체크하고, 해당 위치에 도달한적 없다면 아래와 같이 수행한다.
      1. queue에 다음 위치를 추가한다.
      2. position[다음 위치] = 현 위치
      3. time[다음 위치] = time[현 위치] + 1
5. 4번 내부의 과정을 queue가 빌 동안 반복한다. 다만 해당 조건에 의해 종료될 일은 없다.
   4-1번 과정에 의해 과정이 종료될 것이다.

전체코드:

import java.util.*;

public class 숨바꼭질4_13913번 {
    static int N, K;
    static int[] position;
    static int size;
    static int[] time;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        size = Math.min(Math.max(N,K)*2+1, 100001);
        time = new int[size];
        time[N] = 0;
        position = new int[size];
        Arrays.fill(position, -1);

        bfs();
        System.out.println(time[K]);

        Stack<Integer> stack = new Stack<>();
        while (K != N) {
            stack.push(K);
            K = position[K];
        }
        stack.add(N);
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);

        while (!queue.isEmpty()) {
            int num = queue.poll();
            if (num == K) {
                return;
            }
            if (num+1 < size && position[num+1] == -1) {
                queue.add(num+1);
                position[num+1] = num;
                time[num+1] = time[num] + 1;
            }
            if (num*2 < size && position[num*2] == -1) {
                queue.add(num*2);
                position[num*2] = num;
                time[num*2] = time[num] + 1;
            }
            if (num-1 >= 0 && position[num-1] == -1) {
                queue.add(num-1);
                position[num-1] = num;
                time[num-1] = time[num] + 1;
            }
        }
    }
}

stack에 동생의 위치부터 수빈이의 위치까지 추가한다.
이후, stack에서 하나씩 꺼내주면 '수빈이 → 다음 위치 → ..... → 동생 위치' 가 출력될 것이다.

 

시행착오:

이전 숨바꼭질 코드들은 bfs임에도 queue를 하나 이용하는게 아닌, stack을 두개 이용했다.

내 생각에는 문제가 없지만, bfs가 원하는 과정과는 약간 다를 것이다.

각 노드를 순차적으로 검사하는게 아닌 역순으로 검사하는 느낌일 것이기 때문이다.

아래 코드에서는 queue를 두번 사용했고, 왜 안되는지는 아직도 모르겠다.
time 배열을 이용하는 대신 queue를 하나 더 이용한거 뿐이라고 생각하기 때문이다.

저 방법이 틀렸다면, 비록 좋은 방법으로 푼 것은 아니지만, 내가 푼 숨바꼭질 2 문제도 틀려야 한다고 생각한다.

import java.util.*;

public class 숨바꼭질4_13913번_반례못찾음 {
    static int N, K;
    static int[] position;
    static int size;
    static int time = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        size = Math.min(Math.max(N,K)*2+1, 100001);
        position = new int[size];
        Arrays.fill(position, -1);

        bfs();
        System.out.println(time);

        Stack<Integer> stack = new Stack<>();
        while (K != N) {
            stack.push(K);
            K = position[K];
        }
        stack.add(N);
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    static void bfs() {
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        queue1.add(N);

        while (position[K] == -1) {
            while (!queue1.isEmpty()) {
                queue2.add(queue1.poll());
            }
            while (!queue2.isEmpty()) {
                int num = queue2.poll();
                if (num+1 < size && position[num+1] == -1) {
                    position[num+1] = num;
                    queue1.add(num+1);
                }
                if (num*2 < size && position[num*2] == -1) {
                    position[num*2] = num;
                    queue1.add(num*2);
                }
                if (num-1 >= 0 && position[num-1] == -1) {
                    position[num-1] = num;
                    queue1.add(num-1);
                }
            }
            time++;
        }
    }
}

틀린점이 있다면 알려주세요. ㅜㅜㅜ