[백준] 1697: 숨바꼭질 (BFS) - JAVA

Class 3+ 에센셜

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

 

 

# 문제

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

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

 

# 예제

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

5 17

 

출력

4

 

# 필요개념

현재 위치를 n이라고 할 때, n - 1, n + 1, n * 2만큼 이동하고 이동한 위치는 다시 현재 위치가 되어 해당 작업을 반복한다. 이 점을 보았을 때 BFS를 이용해 풀어야겠다고 생각했다. BFS는 보통의 경우 배열과 큐를 이용해 풀었던 거 같아 그렇게 풀었다.

 

큐에다가 현재 위치를 넣어두고, 이를 꺼내어 n - 1, n + 1, n * 2를 다시 큐에 넣는다.

배열은 이동한 횟수를 넣어주기 위한 int형 1차원 배열로 선언했고, N과 K 모두 100,000 을 넘지 않기 때문에 배열의 크기를 100001로 지정하였다.

 

첫 시작 위치 즉 수빈이의 위치는 이동 횟수가 없기 때문에 0으로 설정해야 하지만 자바는 0이 디폴트값이기 때문에 배열값에 변화를 주지 않고 큐에 넣어두기만 했다.

 

이후에는 while문을 이용해 반복문을 돌려 평범한 bfs 문제를 풀듯이 풀어내었다.

# Code

import java.io.*;
import java.util.*;

public class Main {
    static int[] count = new int[100001];
    static int subin;
    static int sister;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        subin = Integer.parseInt(st.nextToken());
        sister = Integer.parseInt(st.nextToken());

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

    public static int bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while(!queue.isEmpty()) {
            int num = queue.poll();

            // 정답
            if (num == sister) return count[num];

            if (num + 1 <= 100000 && count[num + 1] == 0) {
                queue.add(num + 1);
                count[num + 1] = count[num] + 1;
            }
            if (num - 1 >= 0 && count[num - 1] == 0) {
                queue.add(num - 1);
                count[num - 1] = count[num] + 1;
            }
            if (num * 2 <= 100000 && count[num * 2] == 0) {
                queue.add(num * 2);
                count[num * 2] = count[num] + 1;
            }
        }
        return 0;
    }
}

 

# 결과