[백준]JAVA - 1697번: 숨바꼭질

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

1697번: 숨바꼭질

풀이

처음엔 dfs를 이용해서 접근했지만 시간을 구하는 게 어려워져서 bfs로 접근했다.

문제에서 제시된 수빈이가 이동하는 방법은 총 3가지이다.

 

1. n+1

2. n-1

3. 2n

 

위 방법으로 1초마다 한 번씩 이동할 수 있다.

예제를 통해서 문제를 차근차근 이해해보겠다.

 

1. 초기 상태 (0초)

2. 1초

수빈이가 이동할 수 있는 곳은

n+1 → 6

n-1  → 4

2n   → 10

즉, 수빈이가 1초 후에 위치할 수 있는 곳은 4, 6, 10이다.

3. 2초

2초일 때부터 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이기때문에 방문한 곳은 신경쓸 필요가 없다. 

먼저 인덱스 4의 경우는 3, 5, 8을 방문할 수 있다. 하지만 인덱스 5는 이미 방문한 적이 있기 때문에 시간 값을 그대로 둔다.

다음 인덱스 6의 경우는 5, 7, 10을 방문할 수 있다. 여기선 5와 10은 이미 방문한 적이 있기 때문에 시간 값을 그대로 둔다.

다음 인덱스 10의 경우는 9, 11, 20을 방문할 수 있다. 모두 방문한 적이 없기 때문에 시간 값을 변경한다.

즉, 수빈이가 2초 후에 위치할 수 있는 곳은 3, 7, 8, 9, 11, 20이다.

4. 3초

3초가 지난 경우도 똑같다. 2초가 지난 시점에서의 수빈이 위치에서 -1, +2, *2를 해주면 된다.

문제에서 제시하는 범위는 0 - 100,000 이지만 예제에서 편의상 범위를 0 - 20 이라고 가정하겠다.

인덱스 11의 경우는 2를 곱하면 범위를 넘어선다. 범위를 넘어서는 경우는 그냥 버리면 된다.

5. 4초

위와 같은 방법으로 계속 반복하면 마지막 4초가 지난 시점에서 동생의 위치에 도달할 수 있다.

 

위의 예시처럼 1초씩 시간이 흐르면서 수빈이가 위치할 수 있는 인덱스값을 queue에 넣으면서 차근차근 풀면 된다.

 

<최종코드>

package BOJ;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int times[];
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(st.nextToken()); // 수빈 위치
        int K = Integer.parseInt(st.nextToken()); // 동생 위치
		
        times = new int[100001]; // 방문 여부 겸 걸리는 시간 체크 배열
		
        // 수빈 위치가 동생 위치를 넘겼을 경우
        if (N >= K) System.out.println(N-K);
        else bfs(N, K);
    }
	
    public static void bfs(int N, int K) {
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
		
        int now = 0;
        int next = 0;
        while (!q.isEmpty()) {
            now = q.poll();
			
            for (int i=0; i<3; i++) {
                if (i==0) next = now + 1;
                else if (i==1) next = now - 1;
                else if (i==2) next = 2 * now;
				
                // 동생의 위치에 도달했을 경우
                if (next == K) {
                    System.out.println(times[now]+1);
                    return;
                }
				
                // next 값이 범위 안에 있으면서 방문하지 않은 경우
                if (next > 0 && next < 100001 && times[next] == 0) {
                    q.add(next);
                    times[next] = times[now] + 1;
                }
            }
        }
    }
}