• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

문제: 숨바꼭질 2

단순 BFS로 최단 경로를 구할 수 있을 때, 그 경로의 갯수는 어떻게 구할 수 있을까요?

BFS에서의 최단 경로

BFS는 DFS와 달리, 잘못된 경로 탐색으로 무한루프에 빠지지 않으므로 BFS로만 해결할 수 있는 문제 유형이 있습니다.

  • ex. 숫자 A에서 최소 갯수의 연산자(+,-,*)를 사용해서 숫자 B 만들기

문제 해결 방법

BFS 탐색 시 사용하는 방문 표시를 하는 순서를 바꿔서 해결할 수 있습니다.

  • 일반적으로 최적화를 위해서 다음 인접 노드(상태)를 순회하는 루프문 안에서 방문 표시를 합니다.
for (Integer nxt : graph[node]) {
    if (!visit[nxt]) {
        visit[nxt] = true;
    }
}

별 거 아닌 거 같아도 이게 중요한 이유는 다음과 같습니다.

  • DFS에서 루프문 안에서 방문 표시를 하지 않고, 새로운 DFS 함수가 호출 될 때 방문 여부를 체크하면 그 갯수만큼 함수 콜스택이 쌓여서 stack overflow가 날 수 있습니다.
  • BFS에서 루프문 안에서 방문 표시를 하지 않고, 큐에서 나온 직후에 방문 여부를 체크하면 그 갯수만큼 추가적으로 Queue에 데이터가 쌓여서 메모리 초과가 날 수 있습니다.

큐에서 나온 후 방문 체크

그러나 최단 경로의 갯수를 구할때는 큐에서 나온 후에 방문 표시하는 방법으로 같은 상태를 중복해서 셀 수 있습니다.

  • 인접 노드를 순회하는 루프문 안에서 방문 표시를 하는 경우 해당 상태는 단 한 번만 큐에 들어갑니다.
  • 하지만 큐에서 나온 후 방문 표시를 하면 같은 댑스에 있는 모든 상태는 중복해서 큐에 들어갈 수 있습니다.
    • BFS는 같은 댑스에 있는 상태는 한 번에 모두 탐색하므로 성립하는 성질입니다.
while (!q.isEmpty()) {
    Integer[] now = q.poll();

    int nowTime = now[0];
    int nowPos = now[1];

    visit[nowPos] = true;

    if (nowPos == K && cnt == 0) {
        shortestTime = nowTime;
        cnt++;
    } else if (nowPos == K && nowTime == shortestTime) {
        cnt++;
    }

    //find nxt Node
}

코드

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


public class Main {

    public static int N, K;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nkInfo = br.readLine().split(" ");

        N = Integer.parseInt(nkInfo[0]);
        K = Integer.parseInt(nkInfo[1]);

        int[] result = getShortestPath();

        System.out.println(result[0]);
        System.out.println(result[1]);
    }

    public static int[] getShortestPath() {

        int shortestTime = 0;
        int cnt = 0;
        boolean[] visit = new boolean[100_001];

        Queue<Integer[]> q = new LinkedList<>();

        q.add(new Integer[]{0, N});
        visit[N] = true;

        while (!q.isEmpty()) {
            Integer[] now = q.poll();

            int nowTime = now[0];
            int nowPos = now[1];

            visit[nowPos] = true;

            if (nowPos == K && cnt == 0) {
                shortestTime = nowTime;
                cnt++;
            } else if (nowPos == K && nowTime == shortestTime) {
                cnt++;
            }

            if (safe(nowPos+1) && !visit[nowPos+1]) {
                q.add(new Integer[]{nowTime+1, nowPos+1});
            }

            if (safe(nowPos-1) && !visit[nowPos-1]) {
                q.add(new Integer[]{nowTime+1, nowPos-1});
            }

            if (safe(nowPos*2) && !visit[nowPos*2]) {
                q.add(new Integer[]{nowTime + 1, nowPos*2});
            }
        }

        return new int[]{shortestTime,cnt};
    }

    public static boolean safe(int pos) {
        return 0 <= pos && pos <= 100000;
    }
}