[백준/자바] 13549번: 숨바꼭질 3

문제

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

풀이

• 수빈이는 동생과 1차원 평면에서 숨바꼭질을 하고 있다.
• 수빈이는 현재 점 N에 있고, 동생은 점 K에 있다.
• 수빈이는 걷거나 순간이동을 할 수 있다.
• 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
• 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
• 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하라.

BFS를 활용한 문제

1697번: 숨바꼭질이랑 굉장히 유사한 문제입니다.
다른 점이 하나 있다면, 여기서 순간이동은 0초 후에 이동을 한다는 것입니다.
이 점을 잘 고려해서 문제를 풀면 어렵지 않게 해결할 수 있습니다.

	private static void bfs() {
		visited = new int[100001];
		Arrays.fill(visited, -1);
       	
        Queue<Integer> queue = new ArrayDeque<>();
		queue.add(n); // 시작 좌표 삽입
		visited[n] = 0; // 시작 지점 방문 처리

• 시작 지점에서 순간이동을 해서 갈 수 있는 모든 좌표도 방문처리를 해주어야 하기 때문에, 모든 좌표를 -1로 채워주었습니다.

		while (!queue.isEmpty()) {
			int cur = queue.poll();
			
			if (cur == k) return; // 현재 좌표가 도착 지점이라면 종료
			
			if (cur * 2 <= 100000 && visited[cur * 2] == -1) {
				visited[cur * 2] = visited[cur];
				queue.add(cur * 2);
			}
			
			if (cur - 1 >= 0 && visited[cur - 1] == -1) {
				visited[cur - 1] = visited[cur] + 1;
				queue.add(cur - 1);
			}
			
			if (cur + 1 <= 100000 && visited[cur + 1] == -1) {
				visited[cur + 1] = visited[cur] + 1;
				queue.add(cur + 1);
			}
		}

• 현재 좌표에서 이동할 수 있는 모든 좌표들에 대해 탐색을 시작합니다.
  • 범위 내, 이동하지 않은 좌표
• 주의하실 점은 순간이동 로직이 가장 위에 있어야 합니다.
• 가장 위에 두지 않고 싶다 하시면 Deque를 이용하시면 됩니다. (addFirst)

코드

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

public class Main_13549 {
	static int n, k;
	static int[] visited;
	
	private static void bfs() {
		visited = new int[100001];
		Arrays.fill(visited, -1);
		
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(n);
		visited[n] = 0;
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			
			if (cur == k) return;
			
			if (cur * 2 <= 100000 && visited[cur * 2] == -1) {
				visited[cur * 2] = visited[cur];
				queue.add(cur * 2);
			}
			
			if (cur - 1 >= 0 && visited[cur - 1] == -1) {
				visited[cur - 1] = visited[cur] + 1;
				queue.add(cur - 1);
			}
			
			if (cur + 1 <= 100000 && visited[cur + 1] == -1) {
				visited[cur + 1] = visited[cur] + 1;
				queue.add(cur + 1);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		bfs();
		
		System.out.println(visited[k]);
	}

}