골드2 - 백준 17182 우주 탐사선

백준 우주 탐사선

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

접근방법

이 문제는 행성 간 이동할 때 방향에 따라 이동비용이 다르고 방문했던 곳도 다시 방문할 수 있기 때문에 평범한 MST는 사용할 수 없었다. 따라서 이동해 온 경로와 현재 위치를 기준으로 이동비용을 비교해서 BFS로 최소 비용을 구해나가는 방식을 생각했다.

비트마스킹과 동적 프로그래밍을 이용해서 구현할 수 있었다.

풀이

우선 dp배열을 선언하여 지나온 경로와 현재 위치를 기준으로 최소 이동 비용을 저장하도록 하였다.
while문에서는 현재 inform에서 다음 방문 노드를 결정해주었는데, 이미 방문했던 곳도 다시 방문할 수 있기 때문에 새로운 노드를 방문할 때만 path값을 변경하여 queue에 넣어줬다.

마지막에는 dp배열에 저장되어 있는, 모든 노드 순회 후 끝나는 지점 별로 이동 비용들을 비교해주어 가장 적은 비용을 출력해주었다.

코드

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

using namespace std;
int dp[(1<<10)][10];
int route[10][10];

class inform
{
public:
	int path;
	int cur;
	int cost;
};

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

	int N, start;
	cin >> N >> start;
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cin >> route[i][j];
	}

	queue<inform> q;
	dp[(1 << start)][start] = 0;
	inform start_node;
	start_node.cur = start;
	start_node.path = (1 << start);
	start_node.cost = 0;

	q.push(start_node);

	while (!q.empty())
	{
		int cur = q.front().cur;
		int path = q.front().path;
		int cost = q.front().cost;
		q.pop();

		for (int i = 0; i < N; i++)
		{
			int new_path;
			int new_cost = cost;
			int temp = (1 << i);
			if ((path & temp) == temp)
				new_path = path;
			else
				new_path = path ^ (1 << i);

			new_cost += route[cur][i];

			if (dp[new_path][i] == -1 || dp[new_path][i] > new_cost)
			{
				inform in;
				in.cost = new_cost;
				in.path = new_path;
				in.cur = i;
				dp[new_path][i] = new_cost;
				
				q.push(in);
			}
		}
	}

	int Min = -1;

	for (int i = 0; i < N; i++) {
		if (Min == -1 || Min > dp[(1 << N) - 1][i])
			Min = dp[(1 << N) - 1][i];
	}
	cout << Min << endl;

	return 0;
}

다른 풀이법

비트마스킹, 동적 프로그래밍 이외에 다른 풀이법에 대해서도 찾아보았는데 플로이드-와샬 알고리즘과 DFS를 이용하여 최소 비용을 구하는 방식이었다.
플로이드-와샬 알고리즘을 이용하여 각 노드에서의 최소 이동거리를 구하고, 최소 이동거리로 DFS를 사용하여 모든 노드를 방문해서 가장 적은 비용을 출력하는 방법이다.