12851번 - 숨바꼭질2(bfs)

문제:

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

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

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

 

풀이:

수빈이가 어떤 위치로 이동하기 위해서는 X-1 또는 X+1 또는 2*X 로 이동 할 수 있다.

가장 빠른 시간 안에 찾는 경우의 수를 구해야 하므로 BFS를 사용하면 될 것이다.일일히 진행하며 모든 수를 저장하고, 일일히 꺼내 쓰는 방법은, 너무 많은 저장공간을 요구한다.

그래서 아래와 같이 생각을 해보았다.

 

1. 두개의 스택 stack1, 2를 준비한다. stack1에 미리 수빈이의 위치(1)을 담아놓는다.
   크기가 충분한 sum 배열과 visited 배열도 필요하다. visited 배열은 방문한 적이 있는 점인지를 나타내고,
   sum 배열을 해당 점까지 갈 수 있는 최소 시간을 저장한다.
2. 먼저 stack1을 stack2에 옮겨담는다. 이때, visited를 통해 중복을 제거한다.
3. stack2안에 있는 요소(num)들을 검사한다.
   1. 만일 num이 K 보다 크다면, num-1에 들린적이 있나 보고, 없다면 num-1을 stack1에 넣어준다.
      sum[num-1] += sum[num]을 통해 sum[num-1]에 갈 수 있는 경우의 수를 더해준다.
   2. 그렇지 않다면 점 num+1, num*2, num-1에 들린적이 있나 각각 검사한다.
      만일 갈 수 있다면, 각각의 점 갈 수 있는 경우의 수를 더해주며, stack1에 넣어준다.
      num-1의 경우는 음수가 되지 않는지 검사해줘야 한다.
4. 검사가 끝나면 count(시간)에 1을 더한다.
5. 2~4번 과정을 sum[K]가 0보다 커질때까지 반복한다.

그렇게 작성된 코드는 아래와 같다.

static void bfs() {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    stack1.push(N);
    sum[N] = 1;

    while (sum[K] == 0) {
        while (!stack1.isEmpty()) {
            int num = stack1.pop();
            if (!visited[num]) {
                stack2.add(num);
                visited[num] = true;
            }
        }
        while (!stack2.isEmpty()) {
            int num = stack2.pop();
            if (num > K) {
                if (!visited[num-1]) {
                    sum[num-1] += sum[num];
                    stack1.push(num-1);
                }
            }
            else {
                if (!visited[num+1]) {
                    sum[num+1] += sum[num];
                    stack1.push(num+1);
                }
                if (!visited[num*2]) {
                    sum[num*2] += sum[num];
                    stack1.push(num*2);
                }
                if (num > 0 && !visited[num-1]) {
                    sum[num-1] += sum[num];
                    stack1.push(num-1);
                }
            }
        }
        count++;
    }

}

sum과 visited를 이용한 이유는 아래와 같다.

1. 만일 중복을 허용한다면, Stack의 크기가 너무 커진다. 오류가 발생할 것이다.
   고로 sum[]을 통해 어떤 점을 방문 할 수 있는 경우의 수를 합하여 저장해준다.
   예를 들어 7로 갈 수 있는 경우의 수가 2이고, 9로 갈 수 있는 경우의 수가 2라면, 
   8로 갈 수 있는 경우의 수는 두 경우를 모두 고려해 4가 될 것이다.
2. 만일 이전 시간대에 어떤 점을 방문한 적이 있다면, 해당 점에 다시 방문한다 하더라도 무시해야한다.
   2번째 5를 방문한 것과, 3번째 5를 방문한 것을 똑같이 포함시킨다면,
   3번째 10을 방문할 때, 이 둘을 구분할 수 없게된다. 3초대에 5와 10을 동시에 방문하게 될 수 있다는 말이다.
   하지만 2초대 5를 여러번 방문하는 것은 각각의 경우의 수로 고려해줘야 한다.
   고로 n초대 방문한 점들은 n+1초가 시작하기 바로 전에 표시해준다.

 

전체 코드:

import java.util.*;

public class 숨바꼭질2_12851번 {
    static int N, K;
    static int[] sum;
    static boolean[] visited;
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        int max = Math.max(N, K);

        sum = new int[max + max];
        visited = new boolean[max + max];

        bfs();

        System.out.println(count);

        System.out.println(sum[K]);
    }

    static void bfs() {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        stack1.push(N);
        sum[N] = 1;

        while (sum[K] == 0) {
            while (!stack1.isEmpty()) {
                int num = stack1.pop();
                if (!visited[num]) {
                    stack2.add(num);
                    visited[num] = true;
                }
            }
            while (!stack2.isEmpty()) {
                int num = stack2.pop();
                if (num > K) {
                    if (!visited[num-1]) {
                        sum[num-1] += sum[num];
                        stack1.push(num-1);
                    }
                }
                else {
                    if (!visited[num+1]) {
                        sum[num+1] += sum[num];
                        stack1.push(num+1);
                    }
                    if (!visited[num*2]) {
                        sum[num*2] += sum[num];
                        stack1.push(num*2);
                    }
                    if (num > 0 && !visited[num-1]) {
                        sum[num-1] += sum[num];
                        stack1.push(num-1);
                    }
                }
            }
            count++;
        }

    }
}

sum과 visited 배열의 크기를 정하는 과정을 꼭 고려해야 한다.

수빈이는 동생보다 뒤에 있을 수도, 앞에 있을 수도 있다.

 

시행착오:

sum과 visited를 이용해야 하는 이유중 2번을 생각하다가 잠시 생각이 꼬였다.

결국 sum과 visited를 이용하지 않고, 중복을 허용했고, 메모리가 초과되었다.

또한 수빈이가 동생보다 뒤에 있을 수도, 앞에 있을 수도 있다는 점을 간과했다.

아래는 그렇게 작성된 틀린 코드이다.

import java.util.Scanner;
import java.util.Stack;

public class 숨바꼭질2_12851번_메모리초과 {
    static int N, K;
    static int sum = 0;
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        bfs();

        System.out.println(count);

        System.out.println(sum);
    }

    static void bfs() {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        stack1.add(N);

        while (sum == 0) {
            while (!stack1.isEmpty()) {
                int num = stack1.pop();
                if (num == K) {
                    sum++;
                    while (!stack1.isEmpty()) {
                        if (stack1.pop() == K) {
                            sum++;
                        }
                    }
                    return;
                }
                stack2.add(num);
            }
            while (!stack2.isEmpty()) {
                int num = stack2.pop();
                if (num > K) {
                    stack1.add(num-1);
                } else {
                    stack1.add(num+1);
                    stack1.add(num*2);
                    if (num > 0) {
                        stack1.add(num-1);
                    }
                }
            }
            count++;
        }
    }
}