숨바꼭질 2 골4

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

시간 복잡도 계산
=>  현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다

N이 10^5  임으로  O(N^2) 해결할 수 없고, 그 하위로 풀어야 한다.

BFS는 정점의 개수 10^5, 간선의 수 3개 O(V) 안에 해결 가능하다.

visisted를 while 안과, for문 안 탐색할 때 처리가 가능한데, 이에 대한 이유를 알 수 있었던 문제라고 생각된다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k;
	cin >> n >> k;

	if (n == k) {
		cout << 0 << "\n" << 1;
		return 0;
	}

	queue<pair<int, int>> q;
	bool visit[100001] = { false, };

	q.push({ n, 0 });

	int cnt = 0, t = 0;
	while (!q.empty()) {
		int line = q.front().first;
		int time = q.front().second;
		q.pop();
		visit[line] = true;

		if (line == k) {
			if (cnt == 0) {
				t = time;
				cnt++;
			} else if (cnt > 0 && time == t) {
				cnt++;
			}
		}
		
		int dx[3] = { line - 1, line + 1, 2 * line };
		for (int i = 0; i < 3; i++) {
			int nx = dx[i];

			if (0 <= nx && nx <= 100000 && !visit[nx]) {
				q.push({ nx, time + 1 });
			}
		}
	}

	cout << t << "\n" << cnt;

	return 0;
}