백준 1697번 숨바꼭질

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

 

아이디어:

1. 2차원 BFS

2. x와 y BFS에서 y가 없는 것이라고 생각하고 구현

3. n과 k의 범위가 100000인 것이지 board는 100000이 아니며, 최대 200000을 가정한다.

탐색 범위가 100000을 넘어간 경우엔 어차피 -1만 할 것이고, 게다가 *2로 100000을 벗어난 경우 -1을 계속 하는 것보다 먼저 -1하고 *2하는게 더 시간상 이득이다.

4. n과 k가 같은 경우에 0을 출력할 수 있도록 큐에서 pop()한 뒤, cur == k 를 검사해서 vis[cur]을 출력한다.

 

풀이에선 일부러 for문을 2개로 둬, 내가 쓰던 BFS 틀에서 벗어나지 않고 알아보기 쉽도록 썼다.

즉, 아래 for문은 식별을 위해서이지, 필요 없다.

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

char board[200001];	
int vis[200001];
int dx[2] = { 1, -1};

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, k;
	cin >> n >> k;
	queue<int> Q;

	vis[n] = 0;
	Q.push(n);

	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();

		if (cur == k) {
			cout << vis[cur];
			return 0;
		}

		for (int dir = 0; dir < 2; dir++) {
			int nx = cur + dx[dir];
			if (nx < 0 || nx >= 100001) continue;
			if (vis[nx] > 0) continue;
			vis[nx] = vis[cur] + 1;
			Q.push(nx);
		}
		for (int dir = 0; dir < 1; dir++) {
			int nx = 2 * cur;
			if (nx < 0 || nx >= 100001) continue;
			if (vis[nx] > 0) continue;
			vis[nx] = vis[cur] + 1;
			Q.push(nx);
		}
	}

	return 0;

}