[자바] 백준 12851번: 숨바꼭질2

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

12851번: 숨바꼭질 2

---

저번에 푼 문제는 최단경로를 하나 출력하면 됐는데,

이번에는 최단경로의 개수를 출력해야 한다.

 

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 P13913 {

	static int[] visited = new int[100001];

	static int count = 0;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		bfs(n, k);

		System.out.println(visited[k] - 1);

		if (n == k) {
			System.out.println(1);
			return;
		}

		System.out.println(count);

	}

	static void bfs(int start, int end) {
		visited[start] = 1;

		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);

		while (!q.isEmpty()) {
			int now = q.poll();

			if (visited[end] > 0 && visited[now] >= visited[end])
				return;

			if (now + 1 <= 100000 && (visited[now + 1] == visited[now] + 1 || visited[now + 1] == 0)) {

				q.add(now + 1);
				visited[now + 1] = visited[now] + 1;
				
				if (now + 1 == end) {
					count++;
				}
			}
			if (now - 1 >= 0 && (visited[now - 1] == visited[now] + 1 || visited[now - 1] == 0)) {
				q.add(now - 1);
				visited[now - 1] = visited[now] + 1;
				
				if (now - 1 == end) {
					count++;
				}
			}
			if (now * 2 <= 100000 && (visited[now * 2] == visited[now] + 1 || visited[now * 2] == 0)) {
				q.add(now * 2);
				visited[now * 2] = visited[now] + 1;
				
				if (now * 2 == end) {
					count++;
				}
			}

		}
	}
}

bfs메소드를 약간 수정해서 풀었다

기존에는 visited[next]==0일때, 즉 방문하지 않았을 때만 큐에 현재 위치를 삽입하였는데

여러 경로를 모두 허용하기 위해서 visited[next]==0 || visited[next]==visited[now]+1 일 때 큐에 넣도록 했다.

(visited[next]>visited[now]+1인 경우는 현재 노드를 거쳐 가는것이 더 빠른경우인데, bfs알고리즘 상 이런 상황은 일어나지 않음.

visited[next]<visited[now]+1인 경우는 현재경로가 최단경로가 아니라는 말이 되므로 큐에 넣지 않음

visited[next]==visited[now]+1인 경우는 최단경로인 경우이므로 큐에 넣음) 

 

그리고 now==end이면 count를 증가시켜 최단경로의 수를 계산했다.