백준 1697번 숨바꼭질(자바) - BFS

숨바꼭질 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

132651

37495

23434

25.011%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

---

풀이

1. 입력값 N을 큐에 넣는다.

2. 큐에서 N을 poll한 후 N을 K와 비교한 후 다르다면 N+1, N-1, 2*N 값을 큐에 넣는다. 그 후 count++ 한다.

3. N+1, N-1, 2*N을 각각 K와 비교한 후 K와 다르다면 N+1-1, N+1+1, (N+1)*2 | N-1-1, N-1+1, (N-1)*2 | 2*N-1, 2*N+1, 2*N*2 값을 큐에 넣는다. 그 후 count++한다.(즉, 각 단계가 끝나고 queue가 비워지면 count++ 한다)

4. 이 과정을 반복하고, 중간에 K와 같은 값이 나오면 프린트한 후 break문을 통해 빠져나온다.

 

오답

for (int i = queue.size(); i > 0; i--)을 처음에 for(int i = 0; i < queue.size(); i++)로 썼더니 큐에 숫자들이 들어오면서 큐의 사이즈가 계속해서 증가하기 때문에 틀린 답이 나왔다.

 

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

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        boolean[] visited = new boolean[100001];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);
        visited[N] = true;
        int count = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int num = queue.poll();
                if (num == K) {
                    System.out.println(count);
                    break;
                }
                if (num > 0 && !visited[num - 1]) {
                    queue.offer(num - 1);
                    visited[num - 1] = true;
                }

                if (num + 1 <= 100000 && !visited[num + 1]) {
                    queue.offer(num + 1);
                    visited[num + 1] = true;
                }
                if (num*2 <= 100000 && !visited[num * 2] ) {
                    queue.offer(num * 2);
                    visited[num * 2] = true;
                }
            }
            count++;
        }

    }
}