백준 1697 숨바꼭질(c++)

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

1697번: 숨바꼭질

<코드>

#include <iostream>
#include <queue>
using namespace std;
bool visited[200001] = {false};
int main()
{
	int start,end;
	queue<pair<int,int>>q;
	cin>>start>>end;
	q.push({start,0});
	visited[start] = false;
	while(!q.empty())
	{
		
		int position = q.front().first;
		int success = q.front().second;
		q.pop();
		if(position<0 || position>100000) continue;
		if(position == end) {
			cout<<success<<'\n';
			break;
		}
		if(!visited[position*2])
		{
			visited[position*2] = true;
			q.push({position*2,success+1});
		}
		if(!visited[position+1])
		{
			visited[position+1] = true;
			q.push({position+1,success+1});
		}
		if(!visited[position-1])
		{
			visited[position-1] = true;
			q.push({position-1,success+1});
		}
	}
}

<풀이 과정>

기본 bfs 문제이다. 

각각의 시작좌표와 방문횟수(초기값=0)을 큐에 푸쉬해준다. 그리고 방문할수 있는 경로 (한칸 뒤로(x-1), 한칸 앞으로(x+1), 두배 앞(2*x)으로) 한번씩 각각 이동하고 도착점과 만나게 되면 횟수를 출력해주면 끝이다.

visited(방문 여부)를 false로 초기화하고 방문하게 되는 좌표는 true시켜주면 겹치는 좌표는 넘어가기 때문에 visited 변수를 선언해준 것이다.