BFS로 최단시간 구하기

백준 12851번을 BFS를 이용해 Java로 풀어봤다. 단순히 최단시간만 구하는 것이 아니라 똑같은 최단시간으로 여러 경로가 있다면 가능한 모든 방법의 수도 함께 구해야 하는 문제였다.

이 문제의 로직 자체는 일찍이 구현했지만 ArrayIndexOutOfBounds를 한 8번쯤 내고나서야 뭐가 잘못됐는지 알게됐다. 로컬에서 돌리는 Intelli J에서는 잘 되는데 BOJ 채점은 자꾸 에러를 내서 돌아버리는 줄 알았다.

일단 뭐가 문제였는지는 마지막에 틀린 코드와 맞은 코드를 비교해보며 살펴보자.

이미 방문했으면 무조건 패스?

이전까지의 탐색 문제들은 이미 방문한 바가 있으면 더이상 방문할 필요가 없었지만 이 문제는 그 점이 달랐다. 이미 방문했어도 또 방문할 수도 있고, 혹은 안 할 수도 있다. 뭐 어쩌라는 거지?

그 기준은 동일한 지점을 같은 시각에 재방문하게 되면 또다시 큐에 추가해줘야 하는 것이다. 왜냐면 서로 다른 방식으로 같은 시각에 타겟 지점을 방문한 것이므로 또 다른 경로의 수로서 추가해줘야 하기 때문이다.

이 기준을 적용하기 위해 큐에 추가해줄 때는 방문 정보를 업데이트하지 않고 큐에서 빼낼 때 업데이트해주면 간단하게 해결이 가능하다.

while (!q.isEmpty()) {
            int size = q.size();
            if (cnt != 0) break;

            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                visited[cur] = true; // 이런 식으로 말이다
                ...

하지만 이미 방문했는데 시간이 흐른 후에 해당 지점을 다시 방문하게 될 경우는 큐에 추가해줄 필요 없다. 당연히 더 오래 걸리는 경로일 것이기 때문이다.

시간 계산

같은 시간이 걸리는 지점의 지점들을 한 번에 처리해주고, 그 다음 시간대로 넘어가는 식으로 계산해주면 된다. 따라서 현재 큐의 크기만큼 for문으로 큐에 있는 원소들을 다 처리해주고, 다음 시간대로 넘어가면 된다.

while (!q.isEmpty()) {
            int size = q.size(); // 이런 식으로 말이다
            if (cnt != 0) break;

            for (int i = 0; i < size; i++) { // 현재 큐의 크기만큼 돌려주자
                int cur = q.poll();
                visited[cur] = true; 
                ...

만약 목표지점보다 이미 앞서 있을 경우는 무조건 뒤로 가는 것 외에는 다른 방법이 없기 때문에 bfs()로 처리해줄 필요없이 그냥 main 함수에서 바로 n-k만큼 이동해준 것을 출력하면 된다.

왜 ArrayIndexOutOfBounds 가 계속 떴을까?

아래는 bfs() 내부의 while문만 따온 것이다.

while (!q.isEmpty()) {
            int size = q.size();
            if (cnt != 0) break;

            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                visited[cur] = true;
                int next;

                next = cur - 1;
                if(next==k) cnt++;
                // else if(!visited[next] && next>=0)  q.add(next); => 원래 썼던 코드
                else if(next>=0 && !visited[next])  q.add(next);

                next = cur + 1;
                if(next==k) cnt++;
                // else if(!visited[next] && next<100001)  q.add(next); => 원래 썼던 코드
                else if(next<100001 && !visited[next])  q.add(next);

                next = cur * 2;
                if(next==k) cnt++;
                // else if(!visited[next] && next<100001)  q.add(next); => 원래 썼던 코드
                else if(next<100001 && !visited[next])  q.add(next);
            }
            time++;
        }

위의 주석 처리한 부분을 살펴보면 바로 아랫줄과 서로 살짝 다른 것을 알 수 있다. next의 범위를 먼저 체크하느냐 아니면 visited[next]의 정보를 먼저 체크하느냐. 이 순서가 다르다.

계속 Index 값이 범위를 벗어난다길래, 도저히 이상할 곳이 없는데 한참을 코드를 쳐다봤다. 8번째 틀렸을 때는 육두문자가 나왔다
Debugging 을 진작 했어야 하는데...
입력값으로 (1,4) 를 넣고 디버깅하니까 주석 처리한 코드의 !visited[next]에 ArrayIndexOutOfBounds가 떠있는 것을 확인할 수 있었다. Intelli J에서는 뒤의 next 범위가 어차피 벗어나니까 그냥 넘어갔던 것 같다.

즉, next의 값으로 -1이 들어갈 경우를 생각해보면 되는 거다. 아래 100001 을 넘어가는 경우도 마찬가지다.

결론은... 저 두 조건의 순서를 서로 바꿔주니까 통과됐다... 허무했지만 다시 실수하진 않겠지.... ㅆ..

아래는 내가 제출한 코드다.

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

public class boj12851 {
    static int n, k, cnt = 0, time = 0;
    static boolean[] visited = new boolean[100001];

    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(n);

        while (!q.isEmpty()) {
            int size = q.size();
            if (cnt != 0) break;

            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                visited[cur] = true;
                int next;

                next = cur - 1;
                if(next==k) cnt++;
                else if(next>=0 && !visited[next])  q.add(next);

                next = cur + 1;
                if(next==k) cnt++;
                else if(next<100001 && !visited[next])  q.add(next);

                next = cur * 2;
                if(next==k) cnt++;
                else if(next<100001 && !visited[next])  q.add(next);
            }
            time++;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());
        k = Integer.parseInt(stk.nextToken());

        if (n >= k) {
            System.out.println((n - k) + "\n1");
            return;
        }

        bfs();
        System.out.println(time + "\n" + cnt);
    }
}

오늘 배운 것

변수의 범위를 먼저 체크해준 후에, 그 변수를 활용해주자

// if(!visited[next] && next>=0) 안 돼!
if(next>=0 && !visited[next]) // 요렇게