[Java] 백준 BOJ / 12851번: 숨바꼭질 2

숨바꼭질 2

문제

---

문제 설명

백준의 숨바꼭질 문제와 같은 문제이지만 최단 시간을 구하는것과 그 방법의 개수를 모두 구하는 문제이다.

최단 시간을 구하고 개수를 구해야하기 때문에 BFS 알고리즘을 사용하여 최단 시간을 구하고 다른 방법들을 통해서 도착지에 도착했을 때 최단시간과 같다면 개수를 더해주면 된다.

---

구현

기본적으로 BFS를 구현해야 하니 Queue를 사용하고 시작점부터 Queue에 넣어주면 된다.

시간을 측정하는 방법은 time 배열을 선언해주고 초기값은 1로 설정하고 방문할때마다 해당 배열에 걸린 시간을 저장해주면 된다.

Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
time[start] = 1;

처음으로 목적지인 k에 도착했다면 resultTime을 걸린 시간인 time[cur] - 1로 초기화하고 resultCount를 1로 초기화한다.

그리고 만약 time[cur] - 1 이 resultTime 과 같다면 또 다른 방법으로 같은 시간에 해당 위치에 도착한 것이기 때문에 resultCount 개수를 증가시켜주면 된다.

if (cur == k) {
	//처음 도착한 경우
	if (resultTime == Integer.MAX_VALUE) {
		resultTime = time[cur] - 1;
		resultCount = 1;
	}
	//한번 방문한 경우
	else if (time[cur] - 1 == resultTime) {
		resultCount++;
	}
}

문제에서 이동할 수 있는 곳은 현재 위치의 1칸 전, 현재 위치의 1칸 후, 현재 위치의 2배이다.

그렇기 때문에 nx 배열을 cur - 1, cur + 1, cur * 2 로 선언해준다.

int[] nx = {cur - 1, cur + 1, cur * 2};

새로 Queue에 들어갈 조건은 time[next]가 0 또는 time[next] 가 time[cur] + 1 과 같은 경우다.

각각의 경우는 방문하지 않은 경우와 해당 정점을 다른 경로로 방문했을 때의 시간과 선택한 경로로 방문했을 때의 시간이 같은 경우이다.

이 점을 유의해서 BFS에 들어갈 next를 정해주면 된다.

for (int next : nx) {
	if (next < 0 || next > SIZE) continue;
	if (time[next] == 0 || time[next] == time[cur] + 1) {
		queue.offer(next);
		time[next] = time[cur] + 1;
	}
}

---

코드

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

public class Main_12851 {
    static int n, k;
    static int[] time;
    static int resultTime = Integer.MAX_VALUE, resultCount;
    static int SIZE = 200000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        time = new int[SIZE + 1];

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        bfs(n);

        sb.append(resultTime).append('\n').append(resultCount);
        System.out.println(sb);
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        time[start] = 1;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == k) {
                //처음 도착한 경우
                if (resultTime == Integer.MAX_VALUE) {
                    resultTime = time[cur] - 1;
                    resultCount = 1;
                }
                //한번 방문한 경우
                else if (time[cur] - 1 == resultTime) {
                    resultCount++;
                }
            }

            int[] nx = {cur - 1, cur + 1, cur * 2};

            for (int next : nx) {
                if (next < 0 || next > SIZE) continue;
                if (time[next] == 0 || time[next] == time[cur] + 1) {
                    queue.offer(next);
                    time[next] = time[cur] + 1;
                }
            }
        }
    }
}