[BOJ/백준 1238/C++] 파티

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

1238번: 파티

 

[문제 요약]

- N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

- N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti의 시간을 소비한다.

- 각가의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 이때 학생들은 최단 시간에 오고 간다.

- N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생의 소요 시간을 구하여라

 

[문제 조건]

- 첫째 줄에 N ( 1 ≤ N ≤ 1,000) , M ( 1 ≤ M ≤ 10,000 ) , X가 주어진다.

- 두 번째 줄 부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 필요한 소요시간 T가 들어온다.

- 시작점과 끝점이 같은 경우는 들어오지 않는다. 

- 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

- 시간 제한 1초

- 메모리 제한 128MB

 

[문제 풀이]

(distance_dt 테이블은 distance_dt[i][j] 일때 i정점에서 j정점까지 가는 최단 비용을 의미한다)

최근에 실버1~골드4 단계의 문제들을 풀다가 한번 난이도를 살짝 올려보자는 생각으로 골드3 문제를 선택했는데 생각보다 나쁘지않았다.

 

문제를 읽어보면 제일 중요한 문장은 '이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.' 이거인거 같다. 이 문장을 해석하면 , 모든 정점에서 다른 모든 정점까지 가는 최단거리를 구하여라와 같은 말이다.

 

무슨 말이냐면 예를들어 N이 4라고 가정하자. 그럴때 1에서 나머지 2,3,4로 가는 최단비용을 구하고, 2,3,4도 똑같이 나머지 모든 정점에 대하여 최단거리를 구한다음 distance_dt[start][X] + distance_dt[X][start] 값 중 가장 큰 값이 정답일 것이다.

 

음의 가중치를 갖는 길이 없고 , 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 방법으로는 다익스트라 알고리즘이 있다.

 

그럼 다익스트라가 무엇이냐?

 

먼저 문제에서 주어진 예제를 한번 그려보자

먼저 1번 노드에서 시작해보겠다. 1번 노드를 기준으로 각 정점 별 거리를 배열로 나타내보면

0

4

2

7

위 표와 같이 나타낼 수 있다. 이 표가 의미 하는건 1번 정점에서 다른 정점으로 가는 최소 비용을 의미한다. 이제 다른 정점을 방문하면서 이 배열을 갱신할 것이다. 다음으로 선택되는 노드는 지금까지 갱신한 최소 비용 중 가장 작은 값을 갖는 노드를 선택한다. 위 표 기준에서는 3번 노드가 선택될 것이다.

 

그 다음 3번 정점에서 갈 수 있는 간선들을 확인해 보자

위 그림에서 보면 3번에서 갈 수 있는 정점은 1번과 4번이 있다. 1번은 이미 방문했던 정점이니 패스하고 4번 정점만이 남는다. 여기서 위의 표를 갱신할 것이다. 위 표에서 보면 1번 정점에서 4번 정점으로 바로가는 비용은 7이였다( 1 → 4 ).

하지만 3번 정점을 경유하여 4번으로 가는 비용은 2+4로 총 6의 비용이 든다(1 → 3 → 4). 따라서 기존보다 비용이 더 낮아졌으니 표를 아래와 같이 갱신해준다.

0

4

2

6

이 다음 방문하지 않은 정점 중 가장 비용이 적은 정점은 2번 정점이다.

 

2번 정점를 확인해 보자

2번 정점에서 갈 수 있는 곳은 1번과 3번 정점이다. 하지만 두 정점은 이미 방문을한 상태이니 넘기도록 한다. 왜냐하면 위 그림을 보면 2번 정점을 거쳐 간다하더라도 1번과 3번 정점의 비용이 갱신되는 경우가 없다. 따라서 배열도 유지한채로 넘어간다.

 

0

4

2

6

 

마지막으로 4번 정점을 확인해보면

갈 수 있는 정점이 2번 밖에 없지만 2번은 이미 방문을 했기 때문에 넘어간다.

0

4

2

6

위 표와 같이 "1번 정점에서 다른 정점까지의 최소 비용"이 완성된 모습이다.

 

위와 같은 방법으로 2번, 3번, 4번 정점에도 똑같이 적용시킨뒤 distance_dt[i][X] + distance[X][i](x는 문제에서 주어진 경유하는 정점)값이 가장 큰 값을 출력하면 정답이된다.

 

여기까지는 다익스트라의 기초 설명이다.

 

이제 이 방법을 코드로 옮기면서 최적화를 한번 해보자

 

다익스트라를 짜면서 가장 시간자원을 가장 많이 잡아 먹는 구간은 비용이 가장 적은 정점을 선택하는 순간일 것이다.

여기서 단순히 선형탐색을 이용하면 작성하면 모든 정점을 확인하면서 비용이 가장적은 정점을 찾는 행위를 N번 만큼 반복하니 시간복잡도가 O(N^2)이 형성된다. 하지만 힙 구조를 활용하면 시간복잡도를 O(N * log N) 까지 줄일 수 있다. 특히 선형탐색을 이용하는 방법은 정점은 많은데 간선이 적을때 매우 치명적이게 비효율적으로 작동한다.

 

필자는 우선순위 큐 ( priority_queue ) 를 이용하여 비용이 가장 적은 정점을 선택하는 방법의 시간을 최소화하여 코드를 작성하였다.

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define INF 999999999

using namespace std;

struct cmp {
	bool operator()(pair<int,int> a, pair<int,int> b)
	{
		return a.second > b.second;
	}
};

int n, m, x;
vector<vector<pair<int,int>>> dt;
vector<vector<int>> distance_dt;

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

	cin >> n >> m >> x;
	dt.resize(n + 1);
	distance_dt.resize(n + 1);
	for (int i = 0; i < n + 1; i++) distance_dt[i].resize(n + 1);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j) { distance_dt[i][j] = 0; continue; }
			distance_dt[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++)
	{
		int start, end, cost;
		cin >> start >> end >> cost;

		dt[start].push_back({ end,cost });
	}

	for (int num = 1; num <= n; num++)
	{
		priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
		//정점 방문체크용 배열
		vector<bool> ck(n + 1);
		pq.push({ num,0 });
		while (!pq.empty())
		{
			pair<int, int> tmp = pq.top(); pq.pop();
			int node = tmp.first;
			int distance = tmp.second;
			ck[node] = true;

			for (int i = 0; i < dt[node].size(); i++)
			{
				int next_node = dt[node][i].first;
				int next_dist = dt[node][i].second;

				//이미 방문한 노드는 패스
				if (ck[next_node]) continue;

				int distance_sum = next_dist + distance;
				//경유해서 가는 것이 더 빠르다면 갱신
				if (distance_sum < distance_dt[num][next_node])
				{
					distance_dt[num][next_node] = distance_sum;
					pq.push({ next_node, distance_sum });
				}
			}
		}
	}

	int ans_max = 0;
	for (int i = 1; i <= n; i++)
	{
		ans_max = max(ans_max, distance_dt[i][x] + distance_dt[x][i]);
	}
	cout << ans_max;
}

아마도 선형탐색 방법을 썻으면 시간초과가 떳을 것 같다.

 

굳