[BaekJoon] 1697 숨바꼭질

1.  문제 링크

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

2.  문제

요약

• 수빈이가 현재 점 N에서 동생이 있는 점 K까지 걷거나 순간이동을 하여 이동하려고 합니다.
• 수빈이의 위치가 X일 때 걷는다면 1초 후에 X - 1 또는 X + 1로 이동하고 순간이동을 하면 1초 후에 2 * X의 위치로 이동합니다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 100,000보다 작거나 같은 정수인 N과 0보다 크거나 같고 100,000보다 작거나 같은 정수인 K가 주어집니다.
• 출력: 첫 번째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[] list;
	
	public static int bfs(int su, int younger) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(su);
		int index = su;
		int l = 0;
		list[index] = 1;
		while(!queue.isEmpty()) {
			l = queue.poll();
			if(l == younger) {
				return list[l] - 1;
			}
			if(l - 1 >= 0 && list[l - 1] == 0) {
				list[l - 1] = list[l] + 1;
				queue.offer(l - 1);
			}
			if(l + 1 <= 100000 && list[l + 1] == 0) {
				list[l + 1] = list[l] + 1;
				queue.offer(l + 1);
			}
			if(2 * l <= 100000 && list[2 * l] == 0) {
				list[2 * l] = list[l] + 1;
				queue.offer(2 * l);
			}
		}
		return -1;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		br.close();
		int su = Integer.parseInt(input[0]);
		int younger = Integer.parseInt(input[1]);
		list = new int[100001];
		bw.write(bfs(su, younger) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 해당 위치에서 걸어서 이동하는 경우와 순간이동하여 이동하는 경우 두 가지를 수행하고 수행하여 이동한 위치에서 같은 방법으로 이동하며 동생의 위치에 도달할 때까지 진행합니다.
• 해당 위치까지 오는 데에 이동한 횟수를 나타내는 list 배열을 생성하고 수빈이가 있는 곳에서 한 칸 뒤의 위치, 한 칸 앞의 위치, 2배 앞의 위치 세 경우가 list 내에 존재하고 아직 값이 0이라면, 즉 아직 해당 위치를 방문하지 않았다면 해당 위치의 값을 (현재 위치까지 이동한 값 + 1)로 변경해주고 해당 위치를 BFS를 통해 탐색하기 위해 Queue에 넣어줘 동생의 위치에 도달하거나 Queue가 비워질 때까지 list의 각 위치들을 방문합니다.

1. (문제에서 주어진 최댓값 + 1)의 길이로 list 배열을 생성합니다.
2. 주어진 수빈이의 위치와 동생의 위치를 이용하여 BFS를 통해 수빈이가 동생을 찾는 가장 빠른 시간을 찾습니다.
   1. BFS를 수행하기 위한 Queue를 생성하고 해당 Queue에 수빈이의 위치를 넣어줍니다.
   2. BFS 수행 과정에서 현재 탐색하고 있는 위치를 나타내는 변수 l을 생성하고 수빈이의 위치에 해당하는 list 값을 1로 변경합니다.
   3. Queue가 비워지기 전까지 반복문을 돌며 동생을 찾는 가장 빠른 시간을 찾습니다.
      1. Queue에서 현재 탐색하고자 하는 위치를 뽑아냅니다.
      2. 만약 해당 위치가 동생의 위치와 같다면 동생의 위치에 도달한 것이므로 (동생의 위치에 해당하는 list 값 - 1)을 반환합니다. 그 이유는 수빈이가 위치한 곳의 값을 1로 두었는데 실제로 수빈이가 위치한 곳은 이동을 하지 않고 도달할 수 있는 곳이기 때문에 1을 빼줍니다.
         • 해당 값을 1로 둔 이유는 해당 위치를 방문하였다는 의미 또한 포함하고자 값을 1로 두었습니다.
      3. 그렇지 않다면 현재 탐색하고 있는 위치 한 칸 전 위치가 list 안에 존재하고 해당 위치를 방문하지 않았다면 해당 위치로 이동하여 이동 횟수가 1 증가하였기 때문에 해당 위치의 list 값을 (현재 탐색하고 있는 위치의 list 값 + 1)로 변경하고 Queue에 해당 위치를 넣어줍니다.
      4. 현재 탐색하고 있는 위치 한 칸 후 위치가 list 안에 존재하고 해당 위치를 방문하지 않았다면 해당 위치로 이동하여 이동 횟수가 1 증가하였기 때문에 해당 위치의 list 값을 (현재 탐색하고 있는 위치의 list 값 + 1)로 변경하고 Queue에 해당 위치를 넣어줍니다.
      5. 현재 탐색하고 있는 위치 두 배에 해당하는 위치가 리스트 안에 존재하고 해당 위치를 방문하지 않았다면 해당 위치로 이동하여 이동 횟수가 1 증가하였기 때문에 해당 위치의 list 값을 (현재 탐색하고 있는 위치의 list 값 + 1)로 변경하고 Queue에 해당 위치를 넣어줍니다.
   4. 만약 3번의 반복문에서 Queue가 비워져 반복문이 완료되었는데 동생의 위치까지 도달하지 못했다면 동생의 위치까지 도달할 수 없는 것이므로 -1을 반환합니다.