백준 1697번 C++

백준 1697번 숨바꼭질

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

1697번: 숨바꼭질

정답 코드

#include <iostream> 
#include <queue>
using namespace std;
const int A = 100001;
int arr[A], n, k;
queue<pair<int, int>> q;
int bfs() {
	arr[n] = 1;
	q.push({ n,0 });
	while (!q.empty())
	{
		int pos = q.front().first;
		int time = q.front().second;
		q.pop();
		if (pos == k)
			return time;
		int arr2[3] = { pos + 1, pos - 1, pos * 2 };
		for (int x = 0; x < 3; x++) {
			int newpos = arr2[x];
				if (newpos >= 0 && newpos < A) {
					if (arr[newpos] == 0) {
						q.push({ newpos,time + 1 });
						arr[newpos] = 1;
					}
				}
		}
	}
}
int main()
{
	cin >> n >> k; 	
	cout << bfs(); 	
	return 0;
}

문제 풀이

bfs를 이용해서 풀 수 있는 문제입니다. 보통의 bfs들은 다차원 배열을 이용하지만 이 경우에는 일차원배열을 이용합니다. 먼저 arr[n]=1을 선언합니다. 시작점이라는 의미입니다. 그리고 나서 queue에는 ({n,0})을 삽입합니다. n은 출발점이고 0은 걸린 시간입니다. 이제 q가 빌 때까지 while문을 돌립니다. 만약 pos==k라면 time을
리턴합니다. 그게 아니라면 arr2배열에 움직일 수 있는 범위 3가지를 삽입하고 반복문을 돌립니다. 이 값들을
각각 newpos에 담은 후 이 값이 0보다 크거나 같고 100001보다 작을 때 newpos이 방문한 곳이 아니라면 q에 ({newpos,time+1})을 삽입합니다.
그리고 arr[newpos]=1로 만들어줍니다.
전체적으로 정리하자면 queue를 돌리면서 큐 안의 좌표값과 K가 같으면 time을 리턴해주고 그게 아니라면 새로운 배열에 움직일 수 있는 조건3개를 추가하고 반복문을 돌리면서 제한된 범위 안에서 움직일 수 있도록
하면 됩니다.