BOJ - 1697. 숨바꼭질 (C++)

1697. BFS

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

1697번: 숨바꼭질

 

[풀이]

문제를 보고 BFS라는 것을 알아야 하는 문제이다. 꼭 2차원배열에서 상하좌우로 움직이지 않더라도 1차원배열에서도 앞 뒤로 움직이는 문제를 BFS로 해결할 수 있다. 또한 해당 코드에서 N과 K가 같을 때를 edge case로서 예외처리 해주어야 한다.

#include <bits/stdc++.h>
using namespace std;

int board[1000000];
int vis[1000000];
int N,K;
int dx[2]={-1,1};

int main(){
	ios::sync_with_stdio(0);
	cin >> N >> K;
	queue<int> Q;
	Q.push(N);
	vis[N] = 1;
	
	while(Q.size()){		
		int cur = Q.front(); Q.pop();
		for (int i=0; i<2; i++){
			int nx = cur + dx[i];
			if (nx<0 || nx>=1e6) continue;
			if (vis[nx] != 0) continue;
			if (nx == K) {
				cout << vis[cur];
				exit(0);	
			}
			Q.push(nx);
			vis[nx] = vis[cur] + 1;
		}	
		int nx = cur*2;
		if (nx<0 || nx>=1e6) continue;
		if (vis[nx] != 0) continue;
		if (nx == K) {
			cout << vis[cur];
			exit(0);	
		}
		Q.push(nx);
		vis[nx] = vis[cur] + 1;
	}
	cout << 0;
}