백준[13913]숨바꼭질 4

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

13913번: 숨바꼭질 4

 

 

쉬운 BFS문제이다. 그러므로 여기서는 내가 이 문제를 풀면서 공부한 내용을 적어볼까 한다.

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

using namespace std;

int N, K;
queue<pair<int, vector<int>>> q;
bool visited[100001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;

	if (N >= K) {
		cout << N - K << endl;
		for (int i = N; i >= K; i--) {
			cout << i << ' ';
		}
		return 0;
	}

	vector<int> v;
	q.push({ N, v });
	while (!q.empty()) {
		int x = q.front().first;
		vector<int> nextV = q.front().second;
		q.pop();
		if (x < 0 || x > 100000) {
			continue;
		}
		bool& vis = visited[x];
		if (vis) continue;
		vis = true;
		nextV.push_back(x);
		if (x == K) {
			cout << nextV.size() - 1 << endl;
			for (vector<int>::iterator iter = nextV.begin(); iter != nextV.end(); iter++) {
				cout << *iter << ' ';
			}
			break;
		}
		q.push({ x - 1, nextV });
		q.push({ x + 1, nextV });
		q.push({ x * 2, nextV });
	}


	return 0;
}

위 코드는 내가 스스로 문제를 풀어서 제출한 코드이다. 공부를 위해서 다른 사람들의 코드를 구경하는 동안에 재밌는 점을 발견했다.

 

수빈이는 -1, +1, *2로 이동할 수 있다. 그런데 만약 수빈이가 시간 T에서 이전에 있었던 장소s를 방문한다면, 시간 T에서는 더이상 가장 방법으로 동생을 찾을 수 없다. 그 이유는 시간 t에서 이미 장소 s에 있었더라면 그 방법이 더 빠른 방법이기 때문이다. (t < T) 그렇다면 수빈이는 중복된 장소를 밟을 수 없다. 이 말은 각각의 장소에 대해서 의미있는 독립적인 값을 가질 수 있기때문이다. 무슨 말이냐면 예를 들어보자.

수빈이는 다음과 같은 방법으로 동생을 가장 빨리 찾을 수 있었다.

5 10 9 18 17

그렇다면 arr[17] = 18

arr[18] = 9

arr[9] = 10

arr[10] = 5

arr[5] = -1

이렇게 경로를 하나의 배열만으로 저장할 수 있다. 왜냐하면 N과 K가 바뀌지 않는 한 arr[x]은 절대 변하지 않는다.

x는 시간 t에서 방문했을 것이고 더이상 방문할 수도, 이전에 방문한 기록도 없다.

 

이렇게 경로를 지정하는 변수를 만들면 내 코드처럼 queue에 경로를 push하면서 쓸데없는 시간, 공간낭비를 하지 않을 수 있다.