백준 1697번 : 숨바꼭질

문제 링크

8달 전에 dp를 통해 해결했었던 문제였지만, 오늘 재채점을 통해 틀렸습니다를 받아서 다시 풀게 되었다.

각 좌표를 정점으로, 1초후에 이동할 수 있는 점들을 연결하여 간선을 만들고 BFS를 통하여 n에서 k까지 갈 수 있는 최단경로를 찾음으로써 문제를 해결하였다.

n과 k의 범위가 10^5까지였기때문에, O(V+E)의 시간복잡도를 가지는 BFS로 큰 문제없이 풀 수 있었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>

using namespace std;

int n,k;

const int MAX = 1e5;
const int INF = 987654321;

vector<vector<int>> edge;


int main(int argc, char** argv) {
	scanf("%d %d",&n,&k);
	
	edge = vector<vector<int>>(MAX+1);
	
	for(int i = 0;i<=MAX;i++)
	{
		if(i - 1 >= 0) edge[i].push_back(i-1);
		if(i + 1 <= MAX) edge[i].push_back(i+1);
		if(2*i <= MAX) edge[i].push_back(2*i);
	}
	
	queue<int> q;
	q.push(n);
	
	vector<int> dist(MAX+1,INF);
	dist[n] = 0;
	
	while(!q.empty())
	{
		int cur = q.front();
		q.pop();
		
		for(auto next : edge[cur])
		{
			if(dist[next] == INF)
			{
				dist[next] = dist[cur] + 1;
				q.push(next);
			}	
		}	
	}
		
	printf("%d",dist[k]);
	
	return 0;
}