13549번 - 숨바꼭질3(bfs)

문제:

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

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

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

 

풀이:

수빈이와 동생은 모두 0 ~ 100,000 사이 점에 위치한다. x는 0과 100,000을 넘어갈 수 없다.

그렇다면 BFS와 우선순위 큐를 사용해 수빈이가 가장 먼저 K에 도착하는 순간 그 시간을 반환해주면 될 것이다.

우선순위 큐를 이용하기 위해 아래 클래스를 작성한다.

class Node implements Comparable<Node>{
    int x;
    int time;
    public Node(int x, int time){
        this.x = x;
        this.time = time;
    }
    public int compareTo(Node node){
        return Integer.compare(this.time, node.time);
    }
}

그 이후 아래와 같이 bfs() 코드를 작성해준다.

static int bfs() {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(N, 0));

    while (!pq.isEmpty()) {
        Node node = pq.poll();
        visited[node.x] = true;
        if (node.x == K) {
            return node.time;
        }
        if (node.x * 2 < size && !visited[node.x*2]) {
            pq.add(new Node(node.x*2, node.time));
        }
        if (node.x + 1 < size && !visited[node.x+1]) {
            pq.add(new Node(node.x+1, node.time+1));
        }
        if (node.x - 1 >= 0 && !visited[node.x-1]) {
            pq.add(new Node(node.x-1, node.time+1));
        }
    }
    return -1;
}

• 실질적으로 -1이 return 되는 일은 없다. 한칸씩 이동하면 결국 어디든지 갈 수 있다.
• 우선순위 큐에 새로운 노드를 포함시킬 때, visited[]를 갱신시키지 않는 이유는 예시를 들겠다.
  예를 들어 99 다음에 100을 가기위해서는 1초의 시간이 필요하다.
  하지만 50 다음에 100을 가기위해서는 순간이동 하면된다.
  만일 node(99, time)가 node(50, time)보다 앞에 있을 때, node(100, time+1)를 포함시키고 visited를 갱신시키면,
  node(100, time)이 큐에 저장될 수 있는 기회를 막는 것이다.
  이는 bfs의 기본 규칙에 어긋난다.

 

전체코드:

import java.util.*;

class Node implements Comparable<Node>{
    int x;
    int time;
    public Node(int x, int time){
        this.x = x;
        this.time = time;
    }
    public int compareTo(Node node){
        return Integer.compare(this.time, node.time);
    }
}

public class 숨바꼭질3_13549번 {
    static int N, K;
    static boolean[] visited;
    static int size;

    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);

        visited = new boolean[size];

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

    static int bfs() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(N, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            visited[node.x] = true;
            if (node.x == K) {
                return node.time;
            }
            if (node.x * 2 < size && !visited[node.x*2]) {
                pq.add(new Node(node.x*2, node.time));
            }
            if (node.x + 1 < size && !visited[node.x+1]) {
                pq.add(new Node(node.x+1, node.time+1));
            }
            if (node.x - 1 >= 0 && !visited[node.x-1]) {
                pq.add(new Node(node.x-1, node.time+1));
            }
        }
        return -1;
    }

}

size = Math.min(Math.max(N,K)*2+1, 100001);에 대해 설명하자면,
모든 size를 100001로 통일해도 문제 풀이에는 상관 없지만, N,K가 작은 수일 때, 너무나 비효율적이다.
예를들어 3 -> 5를 가기 위해 3의 배수, 4의 배수를 모두 체크하는 끔찍한 일이 생긴다.

고로 size를 너무 과도하지 않게 설정해놓고 문제를 푸는 편이 효율적이라고 생각한다.

 

시행착오:

이전 문제인 숨바꼭질2의 코드에서 많이 변경하고 싶지 않다는 욕심으로 인해 시간이 오래걸렸다.

우선순위 큐를 이용해서 풀고 싶다는 생각과 숨바꼭질2를 계승하고 싶다는 생각이 둘 다 있었지만,
숨바꼭질 2에게 정이 생겼는지 숨바꼭질 2를 채택했다.

숨바꼭질 2를 이용하다보니 Stack 두개를 이용했고, 이는 시간초과를 불렀다.
또한 조건을 너무나 덕지덕지 붙혀버렸다.
K가 num보다 작은 상황에서는 효과적이겠찌만, 그 이외 상황에선 좋지않은 선택이었다.

조건을 덕지덕지 붙히면서, 생각이 꼬여버려 bfs와 dfs를 이상하게 섞어버렸고, 결국 시간초과가 나오게 되었다.

import java.util.*;

public class 숨바꼭질3_13549번_시간초과 {
    static int N, K;
    static boolean[] visited;
    static int max;
    static int time = 0;

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

        max = Math.max(N, K);

        visited = new boolean[max + max + 1];

        bfs();

        System.out.println(time);
    }

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

        while (!visited[K]) {
            while (!stack1.isEmpty()) {
                stack2.add(stack1.pop());
            }
            while (!stack2.isEmpty()) {
                int num = stack2.pop();
                if (num > K) {
                    if (!visited[num-1]) {
                        stack1.push(num-1);
                        visited[num-1] = true;
                    }
                }
                else {
                    for (int i = num*2; i < max*2; i*=2) {
                        if (i >= max * 2 - 1) {
                            break;
                        }
                        if (i == K) {
                            return;
                        }
                        if (!visited[i]) {
                            nextStep(stack1, num, i);
                            visited[i] = true;
                        }
                    }
                    nextStep(stack1, num, num);
                }
            }
            time++;
        }
    }

    private static void nextStep(Stack<Integer> stack1, int num, int i) {
        if (!visited[i+1]) {
            stack1.push(i+1);
            visited[i+1] = true;
        }
        if (num > 0 && !visited[i-1]) {
            stack1.push(i-1);
            visited[i-1] = true;
        }
    }
}

 

잔머리만 너무 굴리다가, 나쁜 결과가 나버렸다. 문제는 처음부터 정직하게 풀도록 하자.