문제

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

풀이

0부터 100,000까지의 수직선 상에서 현재 위치가 x라면, 수빈이는 x + 1, x - 1, 2 * x 이렇게 3가지 경로로 움직일 수 있다. 각 경로에 대한 가중치가 없는 상태에서, 수빈이가 N에서 K까지 가는 데 걸리는 최소 시간을 구하는 것이므로 BFS를 떠올릴 수 있다!

큐에 현재 수빈이의 좌표 (pos)와 도달 시간 (time)을 같이 저장하여 BFS 탐색을 진행하다가, 수빈이의 좌표가 K과 일치하는 순간 탐색을 종료하면 된다. 그리고 그때의 time 값이 바로 최소 이동 시간이다.

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
#include <queue> 
#include <cstring> 
using namespace std;

const int MAX = 100001; 
bool visited[MAX]; // 특정 좌표의 방문 여부 저장 

int n, k; // 두 사람의 좌표 
queue<pair<int, int>> q; // (좌표, 도달 시간) 

void checkVisited(int pos, int time){
	if(pos >= 0 && pos < MAX){ 
		if(!visited[pos]){ 
			// bfs 경로에 따라 누적해서 time 증가 
			q.push({pos, time + 1}); 
			visited[pos] = true; 
		}
	}
}

void bfs(int start){
	q.push({start, 0}); 
	visited[start] = true; 

	while(!q.empty()){ 
		int x = q.front().first; 
		int time = q.front().second; 
		q.pop();
		
		if(x == k){
			cout << time << endl;
			return;
		}

		checkVisited(x + 1, time); 
		checkVisited(x - 1, time); 
		checkVisited(2 * x, time); 
	}
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	cin >> n >> k;
	
	bfs(n);

	return 0;
}