[백준] 13549 숨바꼭질 3(Gold.5) - BFS

문제

숨바꼭질 3

코드

A → B 문제와 유사한 BFS 문제이다.
큐와 방문 여부 체크를 위한 배열만을 사용하여 풀었다.

• 풀이 방법
  • A → B 문제는 목표 값에 도달하면 그 경로가 정답이므로 해당 경로의 level을 반환한다.
  • 반면 숨박꼭질 3 문제는 목표 값에 도달하는 여러 경로의 이동 시간을 비교하여 이동 시간이 최솟값인 경로의 이동 시간을 출력하는 방식이다.

1. 노드 값과 이동 시간을 저장할 큐를 선언하여 초기 값을 저장한다.

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {start, 0});

2. 큐에서 현재 값을 빼고 - 1, + 1, * 2 연산을 실행한다.

int[] current = queue.poll();
int cLocation = current[0];
int cTime = current[1];
visited[cLocation] = true;

int minus = cLocation -1;
int plus = cLocation +1;
int multiply = cLocation *2;

3. 현재 값이 목표 값이라면 현재 이동 시간과 min값을 비교하여 최솟값을 min에 저장한다.

if (cLocation == target) min = Math.min(min, cTime);

4. 아직 방문하지 않은 노드라면 큐에 현재 노드와 이동 시간을 삽입한다.

if (minus >= 0 && !visited[minus]) {
    queue.offer(new int[] {minus, cTime+1});
}
if (plus <= 100000 && !visited[plus]) {
    queue.offer(new int[] {plus, cTime+1});
}
if (multiply <= 100000 && !visited[multiply]) {
    queue.offer(new int[] {multiply, cTime});
}

5. 모든 경로를 계산했다면 최솟값인 min을 출력한다.

return min;
System.out.println(BFS(N, K));

전체 코드

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

/**
 * 순간 이동(0초): 2*현재 위치
 * 걷기(1초): 현재 위치 -1 or +1
 */
public class _13549 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        System.out.println(BFS(N, K));
    }

    public static int BFS(int start, int target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {start, 0});

        boolean[] visited = new boolean[100001];
        int min = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cLocation = current[0];
            int cTime = current[1];
            visited[cLocation] = true;

            int minus = cLocation -1;
            int plus = cLocation +1;
            int multiply = cLocation *2;

            if (cLocation == target) min = Math.min(min, cTime);

            if (minus >= 0 && !visited[minus]) {
                queue.offer(new int[] {minus, cTime+1});
            }
            if (plus <= 100000 && !visited[plus]) {
                queue.offer(new int[] {plus, cTime+1});
            }
            if (multiply <= 100000 && !visited[multiply]) {
                queue.offer(new int[] {multiply, cTime});
            }
        }
        return min;
    }
}

헷갈리는 부분

분명 모든 경우의 수를 구해야 한다. 그리고 구한 값을 모두 비교하여 최소 이동 시간을 출력해야 한다. 그런데 visited 배열로 방문한 노드는 재방문하지 않는 조건을 달면 목표 값에 최초로 도달하는 값이 정답이 되어 버린다.
만약 목표 값이 17일 경우 최초로 17에 도달하는 경로의 시간이 min에 저장되고 visited[17] = true가 된다. 그럼 17에 도달하는 여러 경로의 시간을 모두 비교하여 최소 값을 min으로 설정해야 하는데 최초 도달 경로 이후에 도달하는 경로는 큐에 삽입하지 않으므로 여러 경로의 시간을 비교하여 최소값을 min에 넣는 것이 아니라 최초로 17에 도달하는 경로의 시간이 min이 되는 것이다. 결국 if (cLocation == target) min = Math.min(min, cTime);가 의미가 없게 된다. if (cLocation == target) {return cTime;} 랑 다를 게 없어진다.

만약 최단 경로를 구하는 문제라면 최초로 도착하는 경로가 정답이지만 위 문제의 경우 순간이동이라는 변수가 있기 때문에 이렇게 구하면 안된다. 근데 또 정답이라고 나온다. 도대체 뭐가 문제인지 모르겠다..... 나중에 한번 더 봐야겠다.

- 아래 사진을 보면 목표 값인 17에 도달하는 경로가 4개 있다. 그러나 위 코드를 실행하면 최초도 도달하는 경로인 "5->4->8->16->17'의 이동 시간이 min에 저장되고 visited[17] = true가 된다. 결국 나머지 경로는 큐에 삽입되지 않고 Math.min()을 통해 비교도 되지 않는다.

• 해결 방법
  • visited 배열을 boolean이 아닌 해당 노드의 이동 시간을 저장한다.
  • 동일 노드로 가는 경로가 있다면 기존의 이동 시간과 새로운 노드의 이동 시간을 비교하여 더 작을 경우 큐에 넣고 이동한다.