[Silver 1] 1697번 숨바꼭질

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

1697번: 숨바꼭질

 

이 문제는 BFS를 사용하면 해결할 수 있다.

 

알고리즘은 다음과 같다.

1. 수빈이가 처음 있는 위치를 queue에 삽입한다.

2. 다음 이동할 수 있는 노드는 수빈이의 위치 - 1, +1 *2 를 queue에 삽입한다. 이때 방문하지 않았거나 100001보다 작아야한다.

3. 이동 중 위치를 찾았다면 시간을 출력한다. 가장 짧은 시간을 출력하라고 했으니 먼저 출력되는 것이 짧은 시간이다.

 

#include <iostream>
#include <queue>
using namespace std;

queue< pair<int,int> > q;
int visited[100001] = {0, };
int N, K, counter = 0;

void bfs(){
	q.push(pair<int,int>(N,0));
	visited[N] = 1;
	while(!q.empty()){
		int now = q.front().first;
		int time = q.front().second;
		q.pop();

		if(now == K){
			cout<<time<<'\n';
			return;
		}
		time += 1;
		for(int i = -1; i<2; i++){
			int index = now + i;
			if(i == 0){
				index = now * 2;
			}
            if(index >= 100001) continue;
			if(!visited[index]){
				q.push(pair<int,int>(index, time));
				visited[index] = 1;
			}
		}

	}
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	cin>>N>>K;
	bfs();
}