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

 

 

문제

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

1697번: 숨바꼭질

 

 

 

 

풀이

BFS 문제이다.

먼저, ①n<k일 경우, ②n>k일 경우, ③n=k일 경우의 세 가지 경우로 나누어 생각했다.

② n>k일 경우, 수빈이는 한 칸씩 뒤로 이동만을 반복하여 동생의 위치(k)에 도달할 수 있다.

    즉, 이 경우 가장 빠른 시간은 오직 'n-k'뿐이다.

 

③ n = k일 경우도 ②의 경우와 마찬가지다. n-k = 0의 시간만이 출력된다.

 

∴ 두 가지 경우로 크게 분리하여, n>=k일 때에는 n-k의 시간을 출력하고, n<k일 경우에는 BFS 알고리즘에 따라 결과값을 출력하도록 한다.

 

BFS 알고리즘

1. 이동 위치를 저장할 큐와 시간을 저장할 배열 visited를 생성한다.

• 이 때, 배열은 100001개로 초기화한다(위치가 0부터 100,000까지 가능하므로).

2. 수빈이의 현재 위치(처음 위치)를 큐에 저장하고, 현재 위치의 visited 값을 1로 한다

• visited의 값들은 모두 0으로 초기화되어 있다. 0인 경우는, 방문하지 않은 경우를 의미하므로 1부터 시작한다.

3. 큐가 빌 때까지 아래의 과정을 반복한다.

4. 큐에서 빼낸 x에 대해 x-1, x+1, 2*x의 위치(next)에 대해 다음을 확인한다.

• next가 동생의 위치(k)와 같다면, x의 시간(visited[x])을 출력하고 종료한다.
• next가 올바른 범위이고(0≤next≤100,000),visited[next]가 0일 경우(next의 위치를 방문하지 않았을 경우), 큐에 next를 저장하고 visited[next]를 visited[x]+1의 값으로 저장한다.
  • 0일 경우에만 visited[next]를 갱신하는 이유는 최솟값을 찾기 위해서이다.

 

 

 

 

코드

import java.util.*;

public class Main {
    private static int n, k;

    private static void BFS(){
        Queue<Integer> queue = new LinkedList<Integer>();
        int[] visited = new int[100001];

		//큐에 초기 위치를 저장하고, 초기 위치의 시간을 1로 초기화
        queue.add(n);
        visited[n] = 1;

		//큐가 빌 때까지 반복
        while(!queue.isEmpty()){
            int x = queue.poll();

            for(int i = 0; i<3; i++){
                int next;

                if(i==0) next = x-1;
                else if(i==1) next = x+1;
                else next = x*2;

				//k와 같은 경우
                if(next ==k) {
                    System.out.println(visited[x]);
                    return;
                }

				//next가 0일 경우(방문하지 않은 경우)
                if(next>=0 && next <=100000 && visited[next] == 0){
                    queue.add(next);
                    visited[next] = visited[x] + 1;
                }
            }
        }
    }

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

		//n>=k라면 n-k를 출력한다(n=k인 경우를 제외하고 BFS 알고리즘으로 출력해도 무방)
        if(n>=k)
            System.out.println(n-k);
        else
            BFS(); //n<k인 경우
    }
}