백준 [N1697 - 숨바꼭질]

문제설명 및 예제 입출력 : https://www.acmicpc.net/problem/1697

 

 

이 문제를 보자마자 BFS로 풀어야겠다고 생각했다. 메모리초과, 시간초과로 몇 번 헤매었는데 그 이유가
"수빈이가 이미 간 경로를 또 확인했다."는 것이다. 이미 방문한 경로는 다시 확인할 필요가 없는 것이 "갈 수 있는 경로 중 가장 빠른 시간"을 구하는 것이기 때문이다. 한번더 확인하게 되면 이전보다 시간이 당연히 늦춰지게 된다.

그래서, 1차원 배열로 방문여부를 확인하고 값은 흐른 시간을 저장하도록 했다.

또한, 수빈이와 동생의 위치가 같을 경우, 수빈이의 위치가 동생의 위치보다 클 경우는 빠르게 결과를 찾을 수 있다.
위치가 같다면 0초, 수빈이 위치가 동생위치보다 클 경우 N-K초 만큼 흐르게 된다.

 

STEP1. 1차원 배열 visited를 초기화해주고 수빈이의 위치 N을 큐에 add해준다.

STEP2. 큐의 poll값(now)이 동생 위치(K)와 같아질 때까지 while문을 돈다.

STEP3. 현재 위치(now)에서 갈 수 있는 위치(now+1, now-1, now*2)가 (1<N,K<100000)의 범위를 벗어나지 않고 visited값이 0일 경우 방문하지 않았던 위치라는 것을 의미한다.
그렇다면, 큐에 갈 수 있는 위치를 저장하고 visited값 또한 visited[now]에서+1해준다.

예) N=5 (0초) -> 갈 수 있는 위치 4, 6, 10 (1초)

visited[4] = visited[5] +1;
visited[6] = visited[5] +1;
visited[10] = visited[5] +1;

visited값은 이전 위치의 값에서 +1하여 흐른 시간을 저장하게 된다.

 

 

소스코드

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

public class Main{
    private static int N;
    private static int K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        if(N==K) System.out.println("0");
        else if(N>K) System.out.println(N-K);
        else {
            System.out.println(bfs());
        }
    }

    private static int bfs() {
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[100001];
        queue.add(N);

        while(!queue.isEmpty()){
            int now = queue.poll();
            if(now==K) break;
            if(now+1<=100000 && visited[now+1]==0){
                queue.add(now+1);
                visited[now+1] = visited[now]+1;
            }
            if(now-1>=0 && visited[now-1]==0){
                queue.add(now-1);
                visited[now-1] = visited[now]+1;
            }
            if(now*2<=100000 && visited[now*2]==0){
                queue.add(now*2);
                visited[now*2] = visited[now]+1;
            }
        }
        return visited[K];
    }
}