문제 이해

숫자 A,B가 주어진다. 나는 A ⇒B로 가고 싶다.

현재 위치가 A라면 A+1, A-1, 2*A로 밖에 이동할 수 없다. 3개의 방법 중 한 방법으로 이동하면 1초가 소요된다.

이 때 B로 가는 최소 시간을 구하는 문제이다.

---

문제 풀이

A,B를 수직선의 한 점으로 생각해보자.
이 때, A+1, A-1, 2*A 점과 A가 연결된 그래프로 생각할 수 있을 것이다.

즉, 가중치가 없는(무조건 1초 걸리기 때문) 그래프에서 최단 거리를 찾는 문제로 해석할 수 있을 것이다.

따라서 BFS를 통해 문제를 해결했다.

---

코드

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

class Sub{
	int x;
	int length;
	public Sub(int x, int length) {
		this.x = x;
		this.length = length;
	}
}

public class Main {
	static int N,K;
	static boolean[] visit = new boolean[100001];
	
	static void dfs() {
		Queue<Sub> queue = new LinkedList<>();
		
		queue.add(new Sub(N,0));
		
		while(!queue.isEmpty()) {
			Sub s = queue.poll();
			
			if(s.x==K) {
                // BFS에서 처음으로 목적지에 도착하면, 
                // 그 때 저장된 거리가 최소 거리
				System.out.println(s.length);
				return;
			}

			if(s.x<0 || s.x > 100000) continue; 
            // 지정된 범위를 넘어가기 때문에 무시
            
			if(visit[s.x]) continue; // 방문한 점이므로 무시
			
			visit[s.x] = true;
			
			queue.add(new Sub(s.x-1, s.length+1));
			queue.add(new Sub(s.x+1, s.length+1));
			queue.add(new Sub(2*s.x, s.length+1));
		}
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		K = sc.nextInt();//N --> K로 가야 함
		
		dfs();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 런타임 에러 이유 : if(visit[s.x])를 if(s.x<0 || s.x>100000)보다 먼저 입력시켜 발생한 문제이다. 항상 배열 범위에 대한 조건 분기문을 먼저 입력하자