[백준] 1697. 숨바꼭질

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

1697번: 숨바꼭질

일차원 그래프의 bfs 문제이다. 주의할 점은 다음과 같다.

• 최소 시간을 구해야 하기 때문에 dfs가 아닌 bfs로 풀어야 한다.
• 최소 시간을 각 그래프의 위치에 저장해준다.
• 한 칸 뒤로 이동, 한 칸 앞으로 이동, 두배 앞으로 이동으로 한 위치당 총 3번의 탐색을 하면 된다.
• 그래프를 벗어나거나 이미 방문한 위치인 경우에는 탐색하지 않는다. (최소 시간을 갱신X)

내가 실수한 부분은 다음과 같다.

while(!que.isEmpty()) {
	Integer idx = que.poll();

	if (idx == k) {
		return;
	}

	// 뒤로
	if (idx - 1 < 0 || map[idx - 1] != 0) { // 잘못 생각한 부분
		continue;
	}
	map[idx - 1] = map[idx] + 1;
	que.add(idx - 1);

	// 앞으로
	if (idx + 1 > 100000 || map[idx + 1] != 0) { // 잘못 생각한 부분
		continue;
	}
	map[idx + 1] = map[idx] + 1;
	que.add(idx + 1);

	// 순간이동
	if (2 * idx > 100000 || map[2 * idx] != 0) { // 잘못 생각한 부분
		continue;
	}
	map[2 * idx] = map[idx] + 1;
	que.add(2 * idx);
}

새로 탐색하려는 위치가 그래프를 벗어나거나 이미 방문한 위치이면 탐색하지 않아야 한다. 그래서 이때 continue를 사용했다. 그런데 문제는 만약 (idx - 1)을 탐색할 때 continue를 하면, (idx + 1)과 (2 * idx)까지 탐색하지 않는다는 것이다! 따라서 이렇게 하면 안된다.

 

그동안 bfs 문제를 풀 때 for문으로 4방면을 탐색하는 경우가 많았는데, 그때는 4방면을 반복문으로 탐색했기 때문에 한 방향을 continue해도 다음 방향을 탐색한다. 따라서 continue를 사용해도 됐었다. 그러나 이번 경우에는 반복문을 사용하지 않고 3가지 탐색의 경우를 나열했기 때문에 continue를 사용하면 안된다! 따라서 다음과 같이 해주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;

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

// 시간복잡도: O(V+E) = 100,000 + 300,000 = 400,000
public class Main {

    static int n; // 수빈 위치
    static int k; // 동생 위치
    static int[] map = new int[100001];

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

        bfs();
        System.out.println(map[k] - 1);
    }

    private static void bfs() {
        Queue<Integer> que = new LinkedList<>();
        map[n] = 1; // 수빈이 위치에 1 저장
        que.add(n);

        while (!que.isEmpty()) {
            Integer idx = que.poll();

            if (idx == k) {
                return;
            }

            // 뒤로
            if (idx - 1 >= 0 && map[idx - 1] == 0) {
                map[idx - 1] = map[idx] + 1;
                que.add(idx - 1);
            }

            // 앞으로
            if (idx + 1 <= 100000 && map[idx + 1] == 0) {
                map[idx + 1] = map[idx] + 1;
                que.add(idx + 1);
            }

            // 순간이동
            if (2 * idx <= 100000 && map[2 * idx] == 0) {
                map[2 * idx] = map[idx] + 1;
                que.add(2 * idx);
            }
        }
    }
}

습관적으로 코드를 작성하지 말고 잘! 생각해야겠다!!!!!!!!