[BOJ] 숨바꼭질 2

[12851] 숨바꼭질 2

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

• 수빈이의 위치 : N
• 동생의 위치 : K
• 동생을 찾는 가장 빠른 시간을 구하는 문제, 그리고 그러한 방법의 개수도 구해야 한다.
• 수빈이가 할 수 있는 행동 (위치 : X)
• 1. 걷기 : X + 1 또는 X - 1로 이동(1초)
• 2. 순간이동 : 2 * X로 이동 (1초)

 

 

Solution

• BFS 풀이 방법
• 경우의 수는 다이나믹 프로그래밍으로 구할 수 있다.
• cnt[i] = i 까지 가는 방법의 개수
• 이미 방문을해서 방문을 할 수 없는 경우에 거리가 같으면 방법의 수만 증가해준다. cnt[next] += cnt[cur];

 

 

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static final int MAX = 100001;
	int n, k;
	int[] dist, cnt;
	boolean c[];
	int min = Integer.MAX_VALUE;

	public void go() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		dist = new int[MAX];
		cnt = new int[MAX];
		c = new boolean[MAX];
		cnt[n] = 1;
		bfs(n);
		System.out.println(dist[k]);
		System.out.println(cnt[k]);
	}

	public void bfs(int n) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(n);
		dist[n] = 0;
		c[n] = true;
		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int next : new int[] { cur * 2, cur + 1, cur - 1 }) {
				if (next >= 0 && next < MAX) {
					if (!c[next]) {
						dist[next] = dist[cur] + 1;
						cnt[next] = cnt[cur];
						c[next] = true;
						q.offer(next);
					} else if (dist[next] == dist[cur] + 1) {
						cnt[next] += cnt[cur];
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}