백준 13913번 숨바꼭질 4 C++ BFS

리뷰

너비우선 탐색을 통하여 해결하는 문제, 최단 거리를 출력하고 그 경로도 기억해 주고 있다가 출력해 줘야 한다.

 

문제 풀이

1. n과 k값을 입력 받고 만약 n가 k보다 클 경우 n - k와 n에서 k까지의 정수를 모두 출력해 준다.
2. 아닐 경우 bfs를 실행해 주고 큐에 정수와 경로를 저장할 pair나 구조체를 활용해 준다.
3. 최단 경로는 방문 배열을 방문하지 않은 곳은 0, 방문할 곳은 현재 이동 횟수 + 1로 해주면 된다.
4. 경로를 벡터에 추가해 주고 큐에 푸시한 후에는 꼭 pop_back을 해줘야 다음 for문 탐사에 문제가 없다.
5. 목적지에 도달한 경우 방문배열의 k인덱스를 출력, 벡터에 들어있는 경로들을 공백을 두고 출력해 준다.

 

참고 사항

테스트 케이스

1 100000
21
1 2 3 6 12 24 48 49 98 196 195 390 780 781 1562 3124 3125 6250 12500 25000 50000 100000

 

해당 케이스가 자꾸 노출되지 않아 구조체를 썼다가 pair를 썼다가 문자열까지 써봤는데 range를 10만이 아닌 100만으로 설정했었다. 배열을 사용할땐 인덱스 오류가 나오질 않으니 조심해서 쓰도록 하자

 

정답 코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int range = 100001;
int v[100001] = { 0, };
int n, k;

void bfs() {
	queue<pair<int, vector<int>>> q;
	q.push({ n, {n}});
	v[n] = 0;

	while (!q.empty()) {
		pair<int, vector<int>> pos = q.front(); q.pop();
		int cx = pos.first;
		vector<int> cp = pos.second;
		if (cx == k) {
			cout << v[k] << "\n";
			for (int i : cp) {
				cout << i << " ";
			}
			return;
		}
		int nxs[3] = {cx - 1, cx + 1, cx * 2};
		for (int nx : nxs) {
			if (0 <= nx && nx < range && !v[nx]) {
				v[nx] = v[cx] + 1;
				cp.push_back(nx);
				q.push({ nx, cp });
				cp.pop_back();
			}
		}
	}
}

int main() {
	cin >> n >> k;
	if (n > k) {
		cout << n - k << "\n";
		for (int i = n; i >= k; i--) {
			cout << i << " ";
		}
	}
	else bfs();
}