[C++] 백준 13913 : 숨바꼭질 4

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

13913번: 숨바꼭질 4

백준 13913번 숨바꼭질 4 를 풀었다.

 

모든 간선의 가중치가 1이고 최단 거리를 찾는 문제여서 BFS 알고리즘을 사용했다.

처음엔 경로를 저장하기 위해서 100001개의 벡터 배열을 만들고 거기에 경로를 저장했는데 메모리 초과가 나왔다.

10만개의 벡터 배열에 평균 경로의 수가 10개라고 쳐도 100만개의 int이고 그러면 400메가의 크기가 된다. 게다가 벡터는 늘어날 때를 대비해 사이즈를 더 잡아서 메모리 초과가 나온 것 같다.

 

그래서 path배열에 이전 경로 1개만 저장하는 방식으로 풀었다.

예제의 입력 n=5, k=17을 예로 들어보면 path배열엔 이렇게 저장된다.

index	5	4	8	16	17
value	0	5	4	8	16

도착 지점 k로부터 이전 경로를 계속 따라가다 보면 출발 지점까지 나온다.

이것을 잘 출력해주면 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, k;
queue<int> q;
int cost[100001];
int visited[100001];
int path[100001];

void BFS() {
	while (!q.empty()) {
		int cur = q.front();
		if (cur == k) break;
		q.pop();
		for (int i = 0; i < 3; i++) {
			int next;
			if (i == 0) {
				next = cur - 1;
			}
			if (i == 1) {
				next = cur + 1;
			}
			if (i == 2) {
				next = cur * 2;
			}

			if (next >= 0 && next <= 100000 && visited[next] == 0) {
				visited[next] = 1;
				cost[next] = cost[cur] + 1;
				path[next] = cur;
				q.push(next);
			}
		}
	}
}

int main() {
	cin >> n >> k;

	if (n > k) {
		cout << n - k << '\n';
		for (int i = 0; i < n - k; i++) {
			cout << n - i << ' ';
		}
		cout << k;
	}
	else {		
		q.push(n);
		visited[n] = 1;
		BFS();
		cout << cost[k] << '\n';
		vector<int> v;
		int next = k;
		v.push_back(k);
		for (int i = 0; i < cost[k]; i++) {
			next = path[next];
			v.push_back(next);
		}
		for (int i = v.size() - 1; i >= 0; i--)
			cout << v[i] << ' ';
	}

	return 0;
}