[백준] 5014. 스타트링크

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

5014번: 스타트링크

• 평소 많이 풀던 BFS 문제에서 4방향 탐색을 2방향 탐색으로 바꾸기만 하면 된다.
• 그런데 다음과 같은 치명적인 실수를 해서 틀렸다.
• BFS를 풀 때 다음과 같이 그래프 범위 밖을 벗어나거나 이미 방문했으면 continue해버렸다. 

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

            // 도착한 경우
            if (num == G) {
                System.out.println(map[G] - 1);
                return;
            }

            // Up
            if (num + U > F || map[num + U] != 0) { // 범위 밖이거나 이미 방문했으면 패스
                continue;
            }
            int newNum = num + U;
            map[newNum] = map[num] + 1;
            que.add(newNum);

            // Down
            if (num - D <= 0 || map[num - D] != 0) { // 범위 밖이거나 이미 방문했으면 패스
                continue;
            }
            newNum = num - D;
            map[newNum] = map[num] + 1;
            que.add(newNum);
        }

 

• 그러나 이렇게 해버리면 UP에서 continue로 패스된 경우 DOWN인 경우까지 탐색하지 못하고 같이 패스하게 된다. 따라서 다음과 같이 작성해주어야, UP에서 continue로 패스되어도 DOWN은 탐색할 수 있다.
• 평소 4방향을 탐색하는 문제에서는 for(int i = 0; i < 4; i++)로 탐색하기 때문에 continue로 패스해도 다음 경우를 탐색했었다. 그러나 이 문제에서는 for문을 사용하지 않기 때문에 continue로 패스하면 그 다음 경우까지 탐색하지 않고 패스한다는 것에 주의하자.

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

// 시간 복잡도: O(V + E) = 1,000,000 + 2 * 1,000,000
public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        int F = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int G = Integer.parseInt(st.nextToken());
        int U = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        // bfs
        int[] map = new int[F + 1];
        map[S] = 1;

        Queue<Integer> que = new LinkedList<>();
        que.add(S);
        while (!que.isEmpty()) {
            Integer num = que.poll();

            // 도착한 경우
            if (num == G) {
                System.out.println(map[G] - 1);
                return;
            }

            // Up
            if (num + U <= F && map[num + U] == 0) {
                int newNum = num + U;
                map[newNum] = map[num] + 1;
                que.add(newNum);
            }

            // Down
            if (num - D > 0 && map[num - D] == 0) {
                int newNum = num - D;
                map[newNum] = map[num] + 1;
                que.add(newNum);
            }
        }

        // 도착하지 못한 경우
        System.out.println("use the stairs");
    }
}