백준 13549번
https://www.acmicpc.net/problem/13549

---

문제

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

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

---

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

---

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

예제 입력 1

5 17

---

예제 출력 1

2

---

생각하기

혹시나 숨바꼭질3 먼저 푸시는 분들은 1, 2부터 풀어보시길 권장드립니다.

숨바꼭질1, 2의 설명링크입니다.
숨바꼭질1

숨바꼭질2

이번 문제는 진짜 오랜만에 정말 골치 아픈 문제였다.
거의 5시간 가까이 붙잡고 있다가 겨우 풀었다.

동작

숨바꼭질 2와 진짜 99프로는 동일하다.

다만 구조를 조금 바꿨는데, 이번에는 Node class를 만들어서
객체형 Queue를 활용해서 풀었다.

이 문제에서 가장 힘들게 풀었던 부분은 아래의 부분이다.

if(range_check() && arr[next_X] > 0) {

		if(time < arr[next_X]) {
			visit[next_X] = false;
		}
}

테스트 케이스 N = 1, K = 16일 때를 한번 생각해보자.

처음 switch 문을 실행하면 +1이 먼저되면서 visit[2] 가 true처리가 되고
이동시간이 1초가 증가하게되면서 1 -> 2 -> 4 -> 8 -> 16 결과로 정답이 1처리가 된다.

즉, 1 * 2 도 2고, 1 + 1도 2인 경우를 해결해야 한다.

나는 여기서 min_time을 Math.min함수에 넣어서 node.time과 비교하여 최소값으로 갱신하면 해결될거라고 생각했는데, visit[2]를 이미 방문해버렸기 때문에 갈 수 없었음..

같은 루트로 가는데, 수빈이가 순간이동을 했을 때, *2는 0초의 시간이기 때문에

N = 1, K = 16 은 정답이 0이 되어야 한다.
결국 이부분을 해결 하기 위해서 위의 코드를 작성했다.

이 코드를 작성함으로써, 최단시간을 알아내기 위해 기존에 있었던, Math.min 함수도 필요없어져서 전체적으로 조금 더 간결해진 느낌이었다.

이 부분을 해결하기 위한 발상이 진짜 별것도 아닌데, 굉장히 어렵게 느껴져서 몇 시간을 붙잡고 있었다.

위의 문제를 해결하기 위해 해당 위치에 도달하기 까지 시간이 얼마나 걸렸는지 저장할 수 있는 배열 arr 을 하나 더 만들었다.

여기서 왜 visit을 int형으로 만들어서 그냥 하나의 배열로 계산하면되는데, 2개의 배열을 만들었나 생각할 수 있다.

이유는 N이 0이고 일때, 시간초과가 출력되서 0을 처리하기가 너무 까다로워서
visit[]과 arr[]의 배열을 구분해서 만들었다.

TMI

정말 짜증나서 포기하고 싶었지만, 끝까지 붙잡고 있었기때문에 정답이라는 결과를 얻을 수 있었던 것 같다
간만에 좀 뿌듯하고, 뭔가 해낸 기분이다.

코딩을 잘 하지는 않지만, 포기하지 않는 자세 하나로 도전하면 이런 성과를 언젠가는 볼 수 있겠지
이 문제는 나중에 백트래킹을 공부하고 다시 한번 풀어보고 싶다.

---

코드

BFS

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

public class Main {
	static int arr[] = new int[100001];
	static boolean[] visit = new boolean [100001];

	static int N, K, next_X;
	static int min_time = Integer.MAX_VALUE / 16;


	public static class Node {
		int X; // 수빈이의 위치
		int time; // 시간(가중치 개념)

		public Node (int X, int time) {
			this.X = X;
			this.time = time;		
		}
	} // End of Node class


	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()); // 수빈이의 위치
		K = Integer.parseInt(st.nextToken()); // 동생의 위치

		if(N >= K) {
			System.out.println(N - K);
			return;
		}


		BFS();


		System.out.println(min_time);

	} // End of main

	private static void BFS() {
        Queue<Node> que = new LinkedList<>();
		que.offer(new Node(N, 0));
		int time;

		while( !que.isEmpty() ) {
			Node node = que.poll();

			if(node.X == K) {
				min_time = node.time;
			}

			for(int i=0; i<3; i++) {
				time = 0;

				switch(i) {
					case 0: next_X = node.X + 1;
							time = node.time + 1;
					 	break;
					case 1: next_X = node.X - 1;
							time = node.time + 1;
						break;
					case 2: next_X = node.X * 2;
							time = node.time;
						break;
				}
				
				if(range_check() && arr[next_X] > 0) {

					if(time < arr[next_X]) {
						visit[next_X] = false;
					}
				}
				
				if(range_check() && visit[next_X] == false) {
					visit[next_X] = true;
					arr[next_X] = time;
					que.offer(new Node(next_X, time));
				}	
				
				
			}
		}
		
	} // End of BFS
	
	private static boolean range_check() {
		return (next_X >= 0 && next_X < 100001);
	} // End of range_check
	
} // End of Main class