🧑🏻‍💻 문제

💡문제 분석 요약

N 과 K 의 숫자 두 개를 입력받는다.
N에서 K까지 이동할 때 걸리는 최소 시간을 구해라. 이동하는 방법은 x-1 x+1 2*x 의 크기만큼 이동할 수 있다.

💡알고리즘 설계

최소 시간이므로 BFS를 활용하여 푼다.
1. Q 를 초기화 하여 각 노드마다 수행 되는 방법이 x-1 x+1 2*x 이렇게 세 가지이므로 여기서 연산된 결과에 대해 방문처리를 진행한다.
한 번씩 Q에서 값을 꺼낼 때마다 count 값을 증가시켜 시간을 구한다.

💡코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 백준_1697_숨바꼭질2 {
	
	static Queue<Integer> q = new LinkedList<Integer>();
	static boolean[] visited = new boolean[100001];
	static int N;
	static int K;
	static int count = 0;
	
	private static void BFS(int a) {
		q.add(a);
		visited[a] = true;
		
		if (a-1 == K || a+1 == K || a*2 == K) {
			System.out.println(0);
			return;
		}
		
		while(!q.isEmpty()) {
			int x = q.poll();
			count++;
			
			if (x-1 == K || x+1 == K || x*2 == K) {
				System.out.println(count);
				return;
			}
			
			if (x-1 > 0 && !visited[x-1]) {
				q.add(x-1);
				visited[x-1] = true;
			}
			
			if (x+1 < 100001 && !visited[x+1]) {
				q.add(x+1);
				visited[x+1] = true;
			}
			
			if (x*2 < 100001 && !visited[x*2]) {
				q.add(x*2);
				visited[x*2] = true;
			}
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		BFS(N);
		
		
	}
}

💡시간복잡도

각 노드에서 세가지의 이동 방식을 구하기 때문에 3N이기에 결과적으로 O(N)이 된다.

💡 틀린 이유

처음에 숫자의 이동 방식이 세 가지 인 건 이해가 됐으나, 이를 어떻게 BFS 로 사용할지 아이디어가 떠오르지 않았다.

다음에도 이동거리의 최소 시간을 구할 땐 이동 방식에 대한 결과 값을 비교하는 식으로 BFS 를 구현해야겠다.