[백준/C++] 숨바꼭질 4

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 예전에 풀었던 숨바꼭질와 거의 다를게 없는 문제다.

 

이동 시간이 항상 같으므로 BFS로 탐색을 시작해 첫 방문하는 경우가 항상 이동 시간이 가장 작다는 것을 알 수 있다.

 

여기서 다른 점은 어떤 경로로 이동을 했는지 출력도 해야한다.

 

그러므로 visited 배열을 만든 뒤 첫 방문을 할 경우 어떤 위치에서 이동했는지 저장을 한다면, 역으로 어떤 경로를 통해 왔는지도 쉽게 구할 수 있다.

 

 

 

 

 

​

[아이디어 정리]

1. 이동 시간이 항상 같으므로 BFS로 탐색을 한다. (첫 방문이 그 위치에 오는 경우 중 가장 이동시간이 작은 경우다.)
2. 첫 방문을 할 때 마다 visited 배열에 어느 위치에서 왔는지 기록한다.
3. 원하는 위치에 도달하면 반복문을 종료하고 비용과 방문한 경로를 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;


int main()
{

	vector<vector<int>> V(100001, vector<int> (3,1000000)); // cost, prev, now
	int a, b;
	cin >> a >> b;
	if (a >= b) {
		cout << a - b << "\n";
		for (int i = a; i >= b; i--) {
			cout << i << ' ';
		}
		return 0;
	}
	queue<vector<int>>q;
	vector<int> nv(3);
	nv[0] = 1, nv[1] = -1, nv[2] = a;
	V[a] = nv;
	q.push(nv);
	int nextN;
	while(true)
	{
		nv = q.front();
		if (nv[2] == b) {
			break;
		}
		q.pop();
		nextN=nv[2] + 1;
		if (nextN<=100000&&nv[0]+1 < V[nextN][0])
		{
			V[nextN][0] = nv[0] + 1;
			V[nextN][1] = nv[2];
			V[nextN][2] = nextN;
			q.push(V[nextN]);
		}
		nextN = nv[2] - 1;

		if (nextN >=0 && nv[0] + 1 < V[nextN][0])
		{
			V[nextN][0] = nv[0] + 1;
			V[nextN][1] = nv[2];
			V[nextN][2] = nextN;
			q.push(V[nextN]);
		}
		nextN = nv[2] * 2;
		if (nextN <= 100000&& nv[0] + 1 < V[nextN][0])
		{
			V[nextN][0] = nv[0] + 1;
			V[nextN][1] = nv[2];
			V[nextN][2] = nextN;
			q.push(V[nextN]);
		}
	}
	int c= nv[0];
	cout << c -1<< endl;
	vector<int> ans(c);
	while(true)
	{
		c--;
		ans[c] = nv[2];
		if (c <= 0) {
			break;
		}
		nv = V[nv[1]];
		
	}
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i]<<" ";
	}


	return 0;
}

 

---

여기에 올린 Code를 보면 공간복잡도의 측면에서 매우 비 효율적으로 작성이 되어있다...

그냥 visited 배열 하나로 풀면 되는데 왜 이전위치, 현재위치, 비용까지 queue에 넣었는지 모르겠다;;

가끔씩 문제를 풀다보면  문제를 비 효율적으로 구현하는 날들이 생기는데 그게 오늘인가?

 

 

 

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