백준 13913_숨바꼭질 4

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

13913번: 숨바꼭질 4

 

해당 문제를 BFS로 바로 접근해서 풀어야한다.

먼저, +1 -1 *2 세 가지 움직임 모두 가중치가 1이고 정점과 간선의 수가 10만개로 많은 편이 아니기 때문이다.

 

BFS로 돌아가는 도중에 check를 통해 들어간 곳을 가지 말아야한다는 조건을 처음에 생각을 못해서 애를 먹었다.

필요한 이유는 BFS는 어차피 앞에서부터 경로를 타고 가기에 후에 나올 경로값이 앞에 나온 경로값보다 무조건 크기에 한 번 간곳은 가지 않아야 효율적인 연산이 된다.

(적절한 표현을 찾지 못하였는데 위에서부터 훑고 오므로 앞에 방문한 값이 더 작을 수 밖에 없다)

간단한 조건이지만 해당 조건이 있어야 다시 들어간 곳을 가지 않기에 불필요한 연산을 하지 않는다

 

추가적으로 경로는 from 배열에 이전 위치를 기록한 다음 

path 배열에 역추적하며 값을 기록한다.

다음 reverse를 통해 뒤집어 출력하면 경로를 출력할 수 있다.

 

 

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

int main() {
	int now, n, k;
	queue<int> q;
	vector<int> path;
	vector<int> d(100001, 0);
	vector<int> from(100001, 0);
	vector<bool> check(100001, false);

	cin >> n >> k;
		
	d[n] = 0, check[n] = true;
	q.push(n);

	// queue가 빌때 까지
	while (!q.empty()) {
		now = q.front();
		q.pop();

		// +1
		if (now < 100000 && !(check[now+1])) {
			check[now + 1] = true;
			d[now + 1] = d[now] + 1; 
			from[now + 1] = now;
			q.push(now + 1);
		}

		// -1
		if (now > 0 && !(check[now - 1])) {
			check[now - 1] = true;
			d[now - 1] = d[now] + 1;
			from[now - 1] = now;
			q.push(now - 1);
		}

		// *2
		if (now*2 <= 100000 && !(check[now * 2])) {
			check[now * 2] = true;
			d[now * 2] = d[now] + 1;
			from[now * 2] = now;
			q.push(now * 2);
		}
	}

	// 경로 추적
	int tr = k;
	while (tr != n) {
		path.push_back(tr);
		tr = from[tr];
	}
	reverse(path.begin(), path.end());

	// print
	cout << d[k] << endl;
	cout << n << " ";
	for (int i = 0; i < path.size(); i++) 
		cout << path[i] << " ";
}