[백준] 1697 - 숨바꼭질

[문제링크]

1697번: 숨바꼭질

 

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

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

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

 

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

 

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

  - BFS는 W초에서 갈수있는 모든 지점을 완료한 후 W+1초의 지점들에 대해 작업하므로, 값의 유/무로만 판단해도 무방하다

  - X번 노드에 도달했을 때의 이동 횟수를 num배열에 저장하여, 그 값이 없는 좌표에 대해서만 진행한다

 

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.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];
		num[N]=1;
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		
		while(num[K]==0) {
			int temp = q.poll();
			if(temp < K && num[temp+1]==0) {
				num[temp+1]=num[temp]+1;
				q.offer(temp+1);
			}
			if(temp-1 >= 0 && num[temp-1]==0) {
				num[temp-1]=num[temp]+1;
				q.offer(temp-1);
			}
			if(temp < K && num[temp*2]==0) {
				num[temp*2]=num[temp]+1;
				q.offer(temp*2);
			}
			
		}
		System.out.println(num[K]-1);
	}
}

결과 화면