[BOJ] 1697 숨바꼭질 [Java]

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

1. 문제 요약

점 N과 점 K가 주어진다. N에서 K로 갈 수 있는 최단시간을 찾는 문제이다.

점 N은 1초마다 +1, -1, *2 위치로 이동할 수 있다.

(0 ≤ N, K ≤ 100,000)

 

2. 풀이

이 문제는 BFS의 깊이를 구하는 문제이다.

예제 5 17을 기준으로, 처음에는 '깊이'를 어떻게 구할까 생각하면서 5에서 17까지 가는 많은 경로 중 가장 짧은 깊이를 출력하는 방법을 생각했다. 하지만 이 방법은 모든 경로를 하나하나 탐색 후 비교해야하므로 비효율적이었다. 

다음으로 생각한 방법은 BFS를 사용하는데, 큐에 깊이도 같이 저장하였다.

17이 있는 깊이를 출력해주고 return하는 방법이다. 이 방법으로 문제를 해결하였다.

'토마토' 문제와 비슷한 느낌이었다. 익는 날짜를 체크하기 위해 깊이를 큐에 같이 저장했다.

일수, 시간 등등을 체크해줄 때는 큐에 깊이도 같이 넘겨주자. 

 

전형적인 BFS 틀을 사용하였고, 델타를 만들어 다음 위치가 +1, -1, *2 인 각각의 좌표를 큐에 넣어줬다.

그런데 제출하면 계속 틀렸다고 나왔다. 내가 놓친 부분은 2가지였다.

1. N이 K보다 큰 위치에 있는 경우

- N > K일 때 K로 갈 수 있는 방법은 -1을 쓰는 것 밖에 없다. 따라서 이 경우에는 조건을 따로 줘야 한다.

- N > K 라면, N - K번 -1해주면 되므로 N-K를 출력해줬다.

2. 깊이가 0부터 시작하지만 시간은 1초부터 시작한다. 그래서 깊이 + 1을 해줘야 했는데, 이것을 main에서 공통으로 출력하는 부분에서 해준게 문제였다. BFS 내에서 return 하기 바로 전 깊이를 변수에 담고 +1을 해줘서 해결했다.

 

-> 델타를 사용하고 깊이를 큐에 같이 저장하면서 BFS를 사용하였다.

 

3. 문제점

 

 

4. 코드

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

public class BOJ_1697_숨바꼭질2 {

	static int[] dir = {1, -1, 2};
	static int[] map;
	static int N, sister, ans, min;
	static boolean[] visited;
	static Queue<Node> queue = new ArrayDeque<> ();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		sister = Integer.parseInt(st.nextToken());
		map = new int[100_000+1];
		visited = new boolean[100_000+1];
		
		
		if (N >= sister) ans = N - sister; //N >= sister 경우 갈 수 있는 방법은 -1밖에 없다
		else bfs(N);
		System.out.println(ans);
		
	}
	
	static void bfs(int start) {
		queue.add(new Node(start, 0));
		visited[start] = true;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			int next = 0;
			for (int d = 0; d < 3; d++) { //델타 사용
				if (d == 2)  next = node.x * 2;
				else next = node.x + dir[d];
				if (next < 0 || next > 100000 || visited[next]) continue;
				if (next == sister) {
					ans = node.depth + 1; //여기시 +1 (초는 1초부터, 깊이는 0부터 시작하므로)
					return;
				}
				visited[next] = true;
				queue.add(new Node(next, node.depth+1)); //큐에 깊이+1을 저장
			}
		}
	}
	
	static class Node {
		int x, depth;
		public Node(int x, int depth) { //시간 == 깊이
			this.x = x;
			this.depth = depth;
		}
	}
}