[백준] 1697. 숨바꼭질 - 실버1

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

1697번: 숨바꼭질

 

문제 요약

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

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

 

문제 해결 아이디어

0 만들기와 비슷한 문제다. bfs로 접근했다. queue에 수빈이의 위치를 넣어주고, 해당 위치를 방문한 것으로 표시했다. 몇 번 이동했는지 체크해 주기 위해 cnt 변수를 함께 queue에 가지고 다녔다. 이동할 위치를 방문하지 않았고 범위 안에 들어와 있다면 방문한 것으로 체크하고 해당 위치를 queue에 넣는 간단한 방법이다.

 

완성된 코드

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

public class Main {
	/*
	 * 120ms
	 */
	
	static boolean visited[];

	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());

		visited = new boolean[100001];
		// 배열의 첫번째 원소: 위치, 두번째 원소: 너비 = 몇초뒤인지
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] { N, 0 });
		visited[N] = true;
		int result = 0;

		while (q.size() > 0) {
			int[] current = q.poll();
			int point = current[0];
			int cnt = current[1];

			if (current[0] == K) {
				result = cnt;
				break;
			}

			if (point - 1 >= 0 && !visited[point - 1]) {
				visited[point - 1] = true;
				q.offer(new int[] { point - 1, cnt + 1 });
			}
			if (point + 1 <= 100000 && !visited[point + 1]) {
				visited[point + 1] = true;
				q.offer(new int[] { point + 1, cnt + 1 });
			}
			if (point * 2 <= 100000 && !visited[point * 2]) {
				visited[point * 2] = true;
				q.offer(new int[] { point * 2, cnt + 1 });
			}
		}
		System.out.println(result);
	}
}