[백준] 13549 - 숨바꼭질 3

[문제링크]

13549번: 숨바꼭질 3

 

비슷한 문제

-숨바꼭질

-숨바꼭질2

 

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

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

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

  - 단, 걷는 방법과 순간이동 방법의 소모 시간이 다르므로, BFS의 형식만 따를 뿐 이론적으로 BFS로 작동하지 않는다

  - ex) +1+1+1+1과 *2 *2 *2 *2는 각각 4번의 이동을 하지만, 소모 시간은 4초 / 0초로 다름

  - 전체 경우의 수를 탐색한다

 

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

 

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

  - 어떤 칸 X에 몇초만에 도달하였는지를 num 배열에 저장하여, 현재의 시간이 더 작을때에만 진행하도록 한다

  - 숨바꼭질 기본 문제와는 달리, 순간이동의 소모 시간이 0이므로, num[X]가 0인지 아닌지만으로는 판단할 수 없다

 

3. 수빈이의 현재 위치가 동생의 위치보다 크다면, +1 *2 연산을 진행할 필요는 없다

  - 마찬가지로, 수빈이의 현재 위치가 동생의 위치보다 작다면, -1 연산을 진행할 필요는 없다

 

4. 정리하자면,

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X+1 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X*2 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신

  - 현재 좌표 X가 동생의 좌표 K보다 크며, X-1 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신하며,

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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];
		Arrays.fill(num, Integer.MAX_VALUE);
		way[N]=1;
		num[N]=0;
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			if(temp < K && num[temp*2]>num[temp]) {
				way[temp*2]+=way[temp];
				if(num[temp*2]!=num[temp]+1)q.offer(temp*2);
				num[temp*2]=num[temp];
			}
			if(temp < K && num[temp+1]>num[temp]) {
				way[temp+1]+=way[temp];
				if(num[temp+1]!=num[temp]+1)q.offer(temp+1);
				num[temp+1]=num[temp]+1;
			}
			if(temp-1 >= 0 && num[temp-1]>num[temp]) {
				way[temp-1]+=way[temp];
				if(num[temp-1]!=num[temp]+1)q.offer(temp-1);
				num[temp-1]=num[temp]+1;
			}
		}
		System.out.println(num[K]);
	}
}

결과 화면