백준 12930 - 두 가중치(C++)

문제

N개의 정점으로 이루어진 그래프 G가 있고, 그래프 G의 모든 간선은 가중치를 2개 가지고 있다.

 

이 말은 특정 노드 i에서 특정 노드 j로 가는 가중치가 2개 있다는 것이다.

 

0번 정점에서 1번 정점으로 가는 최단 경로를 찾아야 한다.

 

경로의 비용은 경로에 있는 간선의 가중치 1을 모두 더한 값인 W1와 가중치 2를 모두 더한 값인 W2를 곱해서 구할 수 있다.

 

여기서 곱하는 것에 유의하며 문제를 풀어야 한다.

입력

첫째 줄에 정점의 수 N이 주어진다. (2 <= N <= 20)

 

둘째 줄부터 N개의 줄에는 그래프의 가중치 1에 대한 정보가, 그 다음 N개의 줄에는 가중치 2에 대한 정보가 주어진다.

 

i번 줄의 j번째 문자는 i에서 j로 가는 간선을 나타낸다. 가중치의 범위는 1~9이며 간선이 없을 때는 '.'으로 나타낸다.

 

예제 입력

4
..14
..94
19..
44..
..94
..14
91..
44..

예제 출력

64

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 정점과 그래프 그리고 최단 거리라는 키워드로 이 문제는 다익스트라 알고리즘을 활용해서 문제를 풀 수 있다는 것을 알았다.

 

하지만 두 개의 가중치가 부여되고 기존에 왔던 각각의 가중치의 누적 거리를 더한 뒤 곱하여 곱해진 값을 구하는 문제이다.

 

이 곱해진 값이 우선순위 큐 내에서 우선순위 기준이 된다.

 

즉, 두 개의 가중치 중 하나라도 더 작은 값을 가진 정점이 있다면 그 값을 우선순위 큐에 집어 넣어야 한다.

 

코드

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

struct Node {
	int idx;
	int pCost;
	int w1;
	int w2;
};

struct cmp {
	bool operator()(const Node a, const Node b)
	{
		if (a.pCost > b.pCost)
			return true;
		else if (a.pCost == b.pCost)
		{
			if (a.idx > b.idx)
				return true;
			else
				return false;
		}
		return false;
	}
};

std::vector<std::pair<int, int> > varr[2][21];
int dist[2][21];
int INF = 1e8;

int Dijkstra(int S, int D)
{
	std::priority_queue<Node, std::vector<Node>, cmp> pq;
	pq.push({S, 0, 0, 0});
	dist[0][S] = 0;
	dist[1][S] = 0;
	while (!pq.empty())
	{
		int here = pq.top().idx;
		int cost = pq.top().pCost;
		int w1 = pq.top().w1;
		int w2 = pq.top().w2;
		pq.pop();
		if (here == D)
			return cost;
		if (w1 > dist[0][here] && w2 > dist[1][here])
			continue;
		for (int i = 0; i < varr[0][here].size(); i++)
		{
			int there = varr[0][here][i].first;
			int nw1 = w1 + varr[0][here][i].second;
			int nw2 = w2 + varr[1][here][i].second;
			int nextDis = nw1 * nw2;
			if (dist[0][there] > nw1 || dist[1][there] > nw2)
			{
				dist[0][there] = std::min(dist[0][there], nw1);
				dist[1][there] = std::min(dist[1][there], nw2);
				pq.push({there, nextDis, nw1, nw2});
			}
		}
	}
	return -1;
}

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N;

	std::cin >> N;
	std::string str;
	for (int i = 0; i < 2 * N; i++)
	{
		std::cin >> str;
		for (int j = 0; j < str.size(); j++)
		{
			if (str[j] != '.')
			{
				if (i >= N)
				{
					varr[1][i % N].push_back(std::make_pair(j, str[j] - '0'));
					varr[1][j].push_back(std::make_pair(i % N, str[j] - '0'));
				}
				else
				{
					varr[0][i % N].push_back(std::make_pair(j, str[j] - '0'));
					varr[0][j].push_back(std::make_pair(i % N, str[j] - '0'));
				}
			}
		}
	}
	for (int i = 0; i < 21; i++)
	{
		dist[0][i] = INF;
		dist[1][i] = INF;
	}
	std::cout << Dijkstra(0, 1) << std::endl;
	return 0;
}

문제 출처

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

12930번: 두 가중치

이론

https://deulee.tistory.com/m/10

다익스트라(Dijkstra) 알고리즘