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

서론

bfs 문제.

풀이

bfs인데 탐색시간을 출력해야한다.

보통 bfs 문제는 2차원 배열을 만들기 때문에 한칸씩 옮겨질때마다 이전칸의 값에서 +1을 해줘서 최종 칸에서의 값을 탐색시간으로 출력해줬는데 이 문제는 배열을 만들지 않는다. (안만들려고 했는데 방문 확인 배열이 없으니 메모리초과를 출력해서 방문 확인 배열은 만들었다.)

그래서 반복문 반복 횟수를 체크했다. 그러나 큐의 반복 횟수를 전부 체크하면 안된다.

int cnt = 0;
while(q.empty()){
	int qSize = q.size();
    while(qSize--){
    	...
    }
    cnt++;
}

cout<<cnt;

첫 시작점은 3개의 점(x-1, x+1, x*2)으로 갈 수 있고, 이 3개의 점은 또 3개의 점으로 갈 수 있다.

1초 후에는 도착지점이 3개

2초 후에는 도착지점이 9개

3초 후에는 도착지점이 27개가 될 것이다.

(도착지점의 중복을 고려하지 않는다고 가정했다.)

마찬가지로 큐의 사이즈도

1초 후에는 3

2초 후에는 9

3초 후에는 27이 될 것이다.

각 초에서 점들이 이동할 수 만큼은 반복 횟수에서 제외해야한다. 이를 외부 반복문에서만 횟수를 증가시키는것으로 해결했다.

구현

n과 k가 같을때에도 반복문을 돌려서 cnt가 증가하는 반례가 있었다.

이를 n과 k가 같으면 무조건 0을 출력하는것으로 수정했다.

//c++

#include <iostream>
#include <queue>

int visited[100001];

int main() {
	int n, k;
	std::queue<int>q;
	std::cin >> n >> k;

	int cnt = 0;
	q.push(n);
	while (!q.empty()) {
		int qSize = q.size();
		bool breakFlag = false;
		while (qSize--) {
			int x = q.front();
			q.pop();
			//std::cout << qSize << " " << x << std::endl;
			int xx1 = x - 1;
			int xx2 = x + 1;
			int xx3 = x * 2;
			if (xx1 == k || xx2 == k || xx3 == k) {
				breakFlag = true;
				break;
			}

			if (xx1 >= 0 && xx1 < 100001 && visited[xx1] == 0) {
				q.push(xx1);
				visited[xx1] = 1;
			}
			if (xx2 >= 0 && xx2 < 100001 && visited[xx2] == 0) {
				q.push(xx2);
				visited[xx1] = 1;
			}
			if (xx3 >= 0 && xx3 < 100003 && visited[xx3] == 0) {
				q.push(xx3);
				visited[xx1] = 1;
			}
		}
		cnt++;
		if (breakFlag == true) break;

	}
	if (n == k) std::cout << 0;
	else std::cout << cnt;
}