숨바꼭질 #1697 c++ 풀이

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

1697번: 숨바꼭질

n에서 k로 가는 최단경로는 BFS를 사용하여 구현할 수 있다.

 

문제는, N에서 K까지 도달하는데 총 몇번 걸렸어? 이다. 이동할때마다 누적해줘야한다.

노드마다 최단거리를 구할수 있다.

 

조금 달랐던 점은 그래프를 초기화하지 않고 그냥 이어져 있다고 가정하는 것이다.

#include <iostream>
#include <string>
#include <cmath> 
#include<vector>
#include<queue>
#include<map>

using namespace std;





//int Graph[101][101];
int visited[100001]; 


int N, K;

void bfs(int start) {


	queue<pair<int, int>> q;
	q.push(make_pair(start, 0));

	visited[start] = 1;

	while (!q.empty())
	{
		int curr = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (curr == K) {
			cout << cnt;
			break;
		}
		if (curr + 1 >= 0 && curr + 1 < 100001) {
			if (visited[curr + 1] == 0) {
				visited[curr + 1] = 1;
				q.push(make_pair(curr + 1, cnt + 1));
			}
		}
		if (curr - 1 >= 0 && curr - 1 < 100001) {
			if (visited[curr - 1]==0) {
				visited[curr - 1] = 1;
				q.push(make_pair(curr - 1, cnt + 1));
			}


		}
		if (curr * 2 >= 0 && curr * 2 < 100001) {
			if (visited[curr * 2]==0) {
				visited[curr * 2] = 1;
				q.push(make_pair(curr * 2, cnt + 1));
			}
		}
	}

	
}
int main() {

	cin >> N >>K;


	bfs(N);

	return 0;
}