백준 13549번: 숨바꼭질 3

문제 설명

• https://www.acmicpc.net/problem/13549
• 앞으로 또는 뒤로 한칸 움직이는 건 1초, x2만큼 순간이동 하는 건 0초가 걸릴 때 N에서 K로 도착하는 최소시간을 구하는 문제입니다.

접근법

• 현재위치에서 순가이동 가능한 위치는 모두 현재시간과 동일합니다.
  • 내가 위치 1까지 5초만에 도달했다면 2,4,8,16,32,64,... 는 모두 5초만에 도달 가능한 거리입니다.
  • 그렇기 때문에 현재 위치(X)에서 조건을 만족한다 가정했을 때 다음 큐에 삽입하는 좌표는 X-1,X+1,2*X 3가지가 아니라 X-1,X+1,2*X,4*X,8*X,16*X,...가 됩니다.

정답

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

public class Main {
	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);
	}

	public static void BFS(int N, int K) {
		Queue<int[]> q = new LinkedList<int[]>();
		int[] v = new int[100_001];
		Arrays.fill(v, -1);
		v[N] = 0;
		q.add(new int[] { N, 0 });
		while (!q.isEmpty()) {
			int[] now = q.poll();
			int num = now[0];
			if (num == K) {
				System.out.println(now[1]);
				return;
			}
			// 순간이동 하는 경우
			while (num <= 100_000) {
				if (num == 0)
					break; // 0은 2를 곱해도 0이라 계속 while문을 탈출하지 못한다
				num *= 2;
				if (num > 100_000) {
					break;
				}
				if (num == K) {
					System.out.println(now[1]);
					return;
				}
				if (v[num] == -1) {
					q.add(new int[] { num, now[1] });
					v[num] = now[1];
				}
			}
			// 뒤로 한칸 움직이는 경우
			num = now[0] - 1;
			if (num >= 0 && v[num] == -1) {
				q.add(new int[] { num, now[1] + 1 });
				v[num] = now[1] + 1;
			}

			// 앞으로 한칸 움직이는 경우
			num = now[0] + 1;
			if (num <= 100_000 && v[num] == -1) {
				q.add(new int[] { num, now[1] + 1 });
				v[num] = now[1] + 1;
			}

		}

	}

}

기타

• 2차원 배열말고 직선에서 움직이는 것도 BFS문제일 수 있다는 걸 잊지말자!!!!