[C++] 백준 1697번 숨바꼭질

 

1) 문제설명

 

백준 Online Judge 1697번 숨바꼭질

 

2) 아이디어

동생을 찾는 가장 빠른 시간을 찾기 위해서 BFS를 사용했다.

시작 지점에서 +1, -1, +현재 좌표로 식을 세워서 BFS 탐색을 실시하면 쉽게 구할 수 있다.

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[100001];
int range[100001];
int cnt = 0;
int dfs(int x, int k) {
	queue <int> q;
	arr[x] = 1;
	q.push(x);
	if (x == k) {
		return 0;
	}
	while (!q.empty()) {
		
		x = q.front();
		
		
		q.pop();
		int dx[] = { -1,1, x };
		for (int i = 0; i < 3; i++) {
			int nx;
			nx = x + dx[i];
			if (nx < 0 || nx > 100000 || arr[nx] == 1) {
				continue;
			}
			else {
				arr[nx] = 1;
				q.push(nx);
				range[nx] = range[x] + 1;
				if (nx == k) {
					return range[nx];
				}
			}
		}
	}
	
}

int main() {
	int n, k;
	cin >> n >> k;
	cout << dfs(n, k);
}