[BFS] 백준 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

수행 시간 : 1시간 30분

 

동생의 위치는 변하지 않고 수빈이의 위치만 변하게 되므로 수빈이의 위치를 받아서 BFS를 돌려주면 되는 문제였다. 다만 아이디어 생각하는데 1시간 이상을 투자했었다. 그리고 범위체크에 신경을 써줘야 예외 케이스에서 오류가 나지 않는다.

 

#include <iostream>
#include <queue>
using namespace std;
bool visited[100001];
int n, k;

int bfs(int x, int y) {
	queue<int> q;
	q.push(x);
	int cnt = 0;
	while (!q.empty()) {
		int s = q.size();
		for (size_t i = 0;i < s;i++) {
			x = q.front();
			q.pop();
			if (x == y) {
				return cnt;
			}
			if (x <= 99999 && visited[x + 1] == false) { // +1 걷기
				q.push(x + 1);
				visited[x + 1] = 1;
			}
			if (x >= 1 && visited[x - 1] == false) { // -1 걷기
				q.push(x - 1);
				visited[x - 1] = 1;
			}
			if (x <= 50000 && visited[x * 2] == false) {
				q.push(x * 2);
				visited[x * 2] = 1;
			}
		}
		cnt++;
	}
}

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