[백준/BOJ] 백준 17182번 : 우주 탐사선

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

17182번: 우주 탐사선

[위치][방문 지금까지 방문한 위치(비트로 표현)] = 최소비용을 저장하여 다익스트라 알고리즘을 이용해 문제를 해결했다.

 

코드

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

int n, k;
vector<pair<int, int>> adj[10];

int Solve(int start, int visited)
{
	vector<vector<int>> result(10, vector<int>(1 << 10, 987654321)); //[위치][방문 지금까지 방문한 위치] = 최소비용
	priority_queue<tuple<int, int, int>> pq; //(-비용, 방문 위치, 현재위치)

	result[start][visited] = 0;
	pq.push(make_tuple(-0, visited, start));

	while (!pq.empty())
	{
		int here = get<2>(pq.top());
		int here_visited = get<1>(pq.top());
		int here_cost = -get<0>(pq.top());
		pq.pop();

		if (result[here][here_visited] < here_cost)
			continue;

		//모든 위치를 다 방문 했을때
		if (here_visited == ((1 << n) - 1))
			return result[here][here_visited];

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_visited = here_visited | (1 << there);
			int there_cost = here_cost + adj[here][i].first;

			if (result[there][there_visited] > there_cost)
			{
				result[there][there_visited] = there_cost;
				pq.push(make_tuple(-there_cost, there_visited, there));
			}
		}
	}

	return -1;
}

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

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			if (i == j)
				continue;

			adj[i].push_back(make_pair(input, j));
		}
	}

	int visited = 0;
	visited |= (1 << k);

	cout << Solve(k, visited);

	return 0;
}