[백준 | Java]1697 숨바꼭질

내 풀이

최단 시간을 구하는 문제이므로 BFS를 사용해 구현하였다.

이 문제 풀이의 핵심은 수빈이가 갈 수 있는 위치 변수 구현이라고 생각한다.
우선 수빈이의 현 위치에서 +1, -1 하는 것은 간단히 dx = {1, -1} 로 나타낼 수 있다.
그렇지만, 수빈이의 현 위치에서 순간이동을 할 때 (수빈이의 현 위치*2) 연산은 변수를 미리 선언해놓으면 계속 바뀌는 현 위치를 받아와야하므로 BFS 진행 과정 내에서 변수선언하여 사용해야한다.

사용 예시는 다음과 같다.

while (!queue.isEmpty()) {
	int dis = queue.poll();
    int[] dx = {1, -1, dis*2 - dis};
    .
    .
    .
}

구현 과정은 다음과 같다.

1. 수빈이와 동생은 한 줄에서 움직이므로 1차원 배열로 그래프 구현
2. BFS 연산 수행
   a. 수빈이가 갈 수 있는 위치 변수 구현 (dx)
   b. 좌우를 탐색해 그래프 내에 있으면서 방문하지 않은 위치를 큐에 삽입, 방문 표시, 시간 +1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int K;
    static int[] graph;

    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());

        graph = new int[100001];

        bfs();

        int result = graph[K];
        System.out.println(result);
    }
    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[100001];

        queue.add(N);
        visited[N] = true;

        while (!queue.isEmpty()) {
            int dis = queue.poll();
            // 수빈이가 갈 수 있는 위치 변수 구현
            int[] dx = {1, -1, dis*2 - dis};

            for (int i = 0; i < 3; i++) {
                int nx = dis + dx[i];

                if (nx >= 0 && nx <= 100000 && !visited[nx]) {
                    queue.add(nx);
                    visited[nx] = true;
                    graph[nx] = graph[dis] + 1;
                }
            }
        }
    }
}