문제 출처

단계별로 풀어보기 > 그래프와 순회 > 숨바꼭질
https://www.acmicpc.net/problem/1697

문제 설명

점 N에서 점 K까지 가는 최소 횟수를 구하라.
단, 이동 할 때는 -1, +1, *2 위치로 이동한다.

접근 방법

bfs를 이용하여 풀이한다.
방문 여부 및 횟수를 판단하는 visited 배열을 생성하고, 점 N에서 bfs를 시작한다. 현재 위치에서 -1, +1, *2 한 경우를 모두 visited에서 방문했는지 판단 후, 방문하지 않은 경우에 q에 삽입한다.
해당 과정을 통해 목표인 k에 도달하면 visited[k]의 값을 출력한다.

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 숨바꼭질 {
    public static int[] visited = new int[100_001];

    public static void bfs(int start, int target){
        Arrays.fill(visited, -1);
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = 0;

        while (!q.isEmpty()) {
            int cur = q.poll();
            if(cur == target) return;

            int[] nexts = {cur - 1, cur + 1, 2 * cur};
            for(int next : nexts){
                if(next < 0 || next > 100_000) continue;
                if(visited[next] != -1) continue;
                visited[next] = visited[cur] + 1;
                q.add(next);
            }

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        bfs(N,K);

        bw.write(String.valueOf(visited[K]));
        bw.flush();
        bw.close();
        br.close();


    }
}

알게된 점

만약 visited[cur]의 값이 visited[cur-1] 등등의 값보다 클 수도 있을까라는 의문을 가진 채로 풀었다. 하지만, 이는 틀린 가정이였다. bfs에서 이미 방문한 경우, 횟수가 현재보다 더 적은 경우 밖에 없다는 것을 알았다.

시간 복잡도는 목표하는 점에 언제 도착할지 모르므로, 전체 범위를 전체 탐사한다는 기준이다. 즉, O(100,000)이 나온다.

문제푼 흔적