[백준] 12851_숨바꼭질2 (자바 JAVA)

[ 문제 ]  [백준] 12851_숨바꼭질2 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

# 접근 방법 및 풀이 

 

• 수빈이의 위치에서 동생의 위치로 -1, +1, *2 일 경우로 이동해보면서 가장 빠른 시간으로 동생의 위치에 도착해야하므로 BFS로 풀었다.
• 숨바꼭질1을 오래전에 풀고, 비슷한 방식으로 최단시간 안에 동생의 위치에 도착하면 카운팅 해서 경우의 수를 세주면 될 줄 알았는데 역시 틀렸다.
• 이 문제의 핵심은 visit체크다.
• 단순히 위치한 곳에 visit[위치] = true해주면 안된다. 왜냐면 같은 위치라도 -1, +1, *2일 때 다른 경로로 도착할 수 있기 때문이다. 그러면 경우의 수가 달라지므로 해당 위치를 visit[] 체크를 중복적으로 허용해주어야한다.
• 그래서 처음에는 단순하게 -1, +1, *2 니까 단순하게 visit[위치][3]으로 3가지의 경우에 따라 해당 위치에 도착하는 부분에 visit체크를 했는데 틀렸다.
• 반례는 1 10을 해보면 된다. 정답은 4 2가 떠야한다. 
• 1 -> 2(+1) -> 4(*2)->5(+1)->10(*2)
• 1 -> 2(*2) -> 4(*2)->5(+1)->10(*2) 
• 이와 같이 2가지 경우의 수가 뜨는데, 경로를 살펴보면 2일때는 +1과 *2로 다른 방식으로 위치에 도착했지만, 4와 5일때는 *2, +1로 같은 방식으로 도착했기 때문에 visit[위치][3가지방법]으로 해서는 안된다.
• 그럼 위치에 대한 visit체크를 무조건 중복 허용으로 해야할까? no. 해당 위치의 visit 체크를 시간으로 비교하면된다!
• 어떤 위치에 방문할 때 동일한 시간으로 방문하는 애들은 큐에 넣어주고, 그보다 더 늦은 시간에 도착하는 애들은 제외한다. 
• 더 늦은 시간에 도착해봤자 최단시간 안에 도착하지 못하므로 제외한다.
• 따라서 visit 배열을 boolean이 아닌 int로 해서 해당 위치에 도착시간을 담는다. visit[3] = 2; 이렇게 3 위치에서 2초만에 도착했다는 시간을 담는다.
• 이렇게 visit배열을 도착한 시간으로 비교해서 풀이해주면 된다.

# 주의할 점 

 

• 단순히 위치에서 visit체크를 할 것이 아니라, 해당 위치에 도착할 수 있는 여러 경우의 수를 따져보기.
• 해당 위치에 도착시간으로 비교해서 도착시간이 같다면 큐에 넣어주고 아니라면 제외
• 1 10 -> 4 2 반례 체크

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj12851_숨바꼭질2 {
	static int N, K, time, cnt;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		bfs();
		System.out.println(time + "\n" + cnt);
	}

	private static void bfs() {
		int visit[] = new int [100001];
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(N, 0));
		visit[N] = 1;
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			if(p.x == K) {
				if(cnt == 0)
					time = p.y; //가장 빠른 시간
				if(time == p.y)
					cnt++; //갯수 증가
				continue;
			}
			int arr[] = {p.x-1, p.x+1, p.x*2};
			for (int i = 0; i < 3; i++) {
				int next = arr[i];
				if(next < 0 || next > 100000)
					continue;
				if(visit[next] == 0 || visit[next] == p.y+1) {
					visit[next] = p.y+1;
					queue.add(new Point(next, p.y+1));
				}
			}
		}
		}
}

 

 

 

REVIEW

정말 좋은 문제다!