[백준] 12851 - 숨바꼭질 2

[문제링크]

12851번: 숨바꼭질 2

 

비슷한 문제

-숨바꼭질

 

0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 + 그 갯수 찾기

  - 3개의 선택지가 있는 탐색 문제.

  - 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용

 

1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다

 

2. 수빈이가 어떤 칸 X에 W초를 거쳐 도달했는데, 이미 해당 칸에 W보다 적은 시간으로 도달한 기록이 있다면, 더이상 탐색하는것은 의미가 없다.

  - 하지만 같은 칸에 동일하게 W초만에 도달했을 경우는 고려해야한다 (가짓수를 구하기 위해)

  - way배열을 두어 W초를 사용해 X번 칸에 도달할 수 있는 가짓수를 저장한다.

 

3. 수빈이의 현재 위치가 동생의 위치보다 크다면, 반드시 작아져야하므로 +1 *2 연산을 진행할 필요 없다

  - 마찬가지로, 수빈이의 현재 위치가 동생의 위치보다 작다면, 반드시 커져야하므로 -1 연산을 진행할 필요 없다

 

4. 정리하자면,

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X+1 좌표에 진행해본 적 없거나 || 현재 이동수 W와 같을때만 진행

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X*2 좌표에 진행해본적이 없거나 || 현재 이동수 W와 같을때만 진행

  - 현재 좌표 X가 동생의 좌표 K보다 크며, X-1 좌표에 진행해본적이 없거나 || 현재 이동수 W와 같을때만 진행하며,

  - K좌표에 도달하는 순간 연산 횟수를 출력, 종료한다

  - 시작할 때 큐의 크기 = W단계에서 연산해야할 크기이므로, 큐의 크기만큼 반복할때마다 1씩 증가하는 act 변수를 두어, 이동 수를 관리한다

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

public class Main{
	public static void main(String[] args)throws Exception {
		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());
		int len=100001;
		int[] num = new int[len*2];
		int[] way = new int[len*2];
		way[N]=1;
		num[N]=1;
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		
		int act=1;
		while(num[K]==0) {
			act++;
			int qlen=q.size();
			for (int i = 0; i < qlen; i++) {
				int temp = q.poll();
				if(temp < K) {
					if(num[temp*2]==0) {
						q.offer(temp*2);
						num[temp*2]=act;					
					}
					if(num[temp*2]==act)way[temp*2]+=way[temp];
				}
				if(temp < K) {
					if(num[temp+1]==0) {
						q.offer(temp+1);
						num[temp+1]=act;						
					}
					if(num[temp+1]==act)way[temp+1]+=way[temp];
				}
				if(temp-1 >= 0) {
					if(num[temp-1]==0) {
						q.offer(temp-1);
						num[temp-1]=act;						
					}
					if(num[temp-1]==act)way[temp-1]+=way[temp];
				}
			}
		}
		System.out.println(num[K]-1);
		System.out.println(way[K]);
	}
}

결과 화면