[BOJ] 백준 12851번 숨바꼭질 2 (Java)

#12851 숨바꼭질 2

난이도 : 골드 5

유형 : BFS

12851번: 숨바꼭질 2

▸ 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

▸ 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

▸ 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

문제 풀이  

BFS를 활용한 그래프 탐색 문제이다. 다만 그래프가 1차원적이라는 것과 중복방문이 가능하다는 특징이 있다. 그래서 한 좌표(x)만을 가지고 최단 경로를 탐색해주면 된다.

 

BFS 탐색은 최단거리를 탐색해준다. 문제에서는 단지 최단거리 뿐만 아니라 방법의 수까지 묻는다. 그러므로 방문체크를 통해 경로 가지치기를 하면 안되고 경로 탐색의 수(move)를 가지고 가지치기를 해야한다. 즉, pos라는 좌표에 해당 탐색이 몇 번째로 왔는가를 확인하고 처음으로 도착했거나 이전 탐색보다 더 빠르게 도착한 경우에만 새로운 경로 탐색을 허용하는 것이다.

 

1. n을 시작으로 bfs탐색을 시작한다. 
2. 이동방법은 총 3가지이다.
   1. pos-1, pos+1, pos*2 순서 상관없이 빠르게 도착하는 것만 탐색하면 된다.
3. 아래 두가지 조건에 해당하는 경우만 다음 탐색을 허용한다.  q.add(next);
   
   1. 첫 방문인 경우, if(move[next] ==0)
   2. 이전 방문보다 더 빠르게 도착했을 경우, if(move[next] >= move[pos] + 1) 
4. 이전 탐색보다 빠르게 도착지에 도착했다면 최솟값을 갱신하고 카운트를 해준다. if(move[pos]<=res && pos == destination) 
   1. res = move[pos];
   2. cnt++;
5. 4번에서 구한 res보다 더 많이 움직인 탐색은 어차피 최솟값 탐색이 안되므로 강제 종료시킨다. if(res < move[pos]) return;

 

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int[] dx = {-1, 1, 2};
	static int cnt=0, res = Integer.MAX_VALUE;
	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(res);
		System.out.println(cnt);
	}
	
	static void bfs(int start, int destination) {
		Queue<Integer> q = new LinkedList<>();
		int[] move = new int[100_001];
		q.add(start);
		
		while(!q.isEmpty()) {
			int pos = q.poll();
			
			if(res < move[pos]) return;
			if(move[pos]<=res && pos == destination) {
				res = move[pos];
				cnt++;
			}

			for(int i=0; i<3; i++) {
				int next = pos;
				if(i==2) {
					next = pos*dx[i];
				}else {
					next = pos + dx[i];	
				}
				
				if (next>=0 && next <100001) {
					if(move[next] ==0 || move[next] >= move[pos] + 1) {
						move[next] = move[pos]+1;
						q.add(next);
					}
				}
			}
		}
	}
}