백준 : 1238번 파티 다익스트라(c++)

백준 링크

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

1238번: 파티

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	39526	19941	13381	48.199%

문제

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

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

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

코드 풀이

나의 풀이

문제를 읽어보면 N개의 마을에 한 명의 학생이 살고있고 그 학생들이 X에 위치한 마을에서 파티를 벌이기로해 X에 모이는 시간과 다시 돌아가는 시간의 총합이 가장 시간을 찾는 문제이다.

1. 모든 정점(마을)에서부터 X까지 걸리는 시간을 구한다(N번의 다익스트라 필요)
2. X에서부터 다시 돌아가는 시간을 구한다.(1번의 다익스트라 필요)

위와 같은 방식으로 풀이를 해서 제출한 결과 통과는 했다.

하지만 제출 결과 시간이 너무 긴것을 확인했고 모든정점을 꼭 거쳐야하나 생각이 들며 구글링을 한 결과

다익스트라 두 번만으로 해결이 가능한것을 확인했습니다.

 

다른 블로거의 최적화된 풀이

1. Graph노드를 연결할때 역방향을 추가하기위해 1차원을 추가하여 역방향 간선을 추가로 입력
2. X노드를 시작지점으로 생각하고 1번(순방향) 다익스트라 1번 진행
3. X노드를 시작지점으로 생각하고 0번(역방향 다익스트라 1번 진행
4. 값 갱신 후 출력

 

나의 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

#define INTMAX 2147483647
#define MAX 1001

vector<pair<int, int>> Graph[MAX];
int Dist[MAX];
int CostSave[MAX];

int Dijkstra(int StartNode, int X)
{
	fill(Dist, Dist + MAX, INTMAX);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, StartNode });
	Dist[StartNode] = 0;

	while (!pq.empty())
	{
		int CurNode = pq.top().second;
		int CurCost = pq.top().first;
		pq.pop();

		if (Dist[CurNode] < CurCost)
			continue;

		int Size = static_cast<int>(Graph[CurNode].size());
		for (int i = 0; i < Size; ++i)
		{
			int NextNode = Graph[CurNode][i].first;
			int NextCost = Graph[CurNode][i].second + CurCost;

			if (Dist[NextNode] > NextCost)
			{
				pq.push({ NextCost, NextNode });
				Dist[NextNode] = NextCost;
			}
		}
	}

	return Dist[X];
}

int main()
{
	int N, M, X;
	int answer = -1;

	cin >> N >> M >> X;

	// 그래프 연결
	for (int i = 0; i < M; ++i)
	{
		int A, B, Cost;
		cin >> A >> B >> Cost;
		Graph[A].push_back({ B, Cost });
	}

	// 모든 사람이 X지점까지 가는 다익스트라 실행
	for (int i = 1; i <= N; ++i)
	{
		CostSave[i] = Dijkstra(i, X);
	}
	// X지점에서 각각의 집까지의 다익스트라 실행
	Dijkstra(X, X);

	// 최고값 갱신
	for (int i = 1; i <= N; ++i)
	{
		CostSave[i] += Dist[i];
		answer = max(answer, CostSave[i]);
	}

	cout << answer;

	return 0;
}

다른 블로거 코드 참조 후 재해석(최적화)

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

#define INTMAX 2147483647
#define MAX 1001

vector<pair<int, int>> Graph[2][MAX];  // 그래프를 순방향 및 역방향으로 나눠서 저장
int Dist[2][MAX];  // 각 방향에서의 최단 거리를 저장할 배열
int CostSave[MAX];

void Dijkstra(int Dir, int X)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, X});  // 시작 노드 X로부터의 거리가 0인 상태로 우선순위 큐에 추가
    Dist[Dir][X] = 0;  // 시작 노드 X의 최단 거리를 0으로 초기화

    while (!pq.empty())
    {
        int CurNode = pq.top().second;  // 현재 노드
        int CurCost = pq.top().first;   // 현재 노드까지의 최단 거리
        pq.pop();  // 최소 거리를 가진 노드를 우선순위 큐에서 제거

        // 이미 계산된 최단 거리보다 더 큰 거리로 왔다면 무시
        if (Dist[Dir][CurNode] < CurCost)
            continue;

        int Size = static_cast<int>(Graph[Dir][CurNode].size());
        for (int i = 0; i < Size; ++i)
        {
            int NextNode = Graph[Dir][CurNode][i].first;  // 다음 노드
            int NextCost = Graph[Dir][CurNode][i].second + CurCost;  // 다음 노드까지의 거리

            // 다음 노드까지의 거리가 더 짧다면 최단 거리 갱신하고 큐에 추가
            if (Dist[Dir][NextNode] > NextCost)
            {
                pq.push({NextCost, NextNode});
                Dist[Dir][NextNode] = NextCost;
            }
        }
    }
}

int main()
{
    int N, M, X;
    int answer = -1;

    cin >> N >> M >> X;

    // 그래프 연결
    for (int i = 0; i < M; ++i)
    {
        int A, B, Cost;
        cin >> A >> B >> Cost;
        Graph[0][A].push_back({B, Cost});  // 역방향 그래프 저장
        Graph[1][B].push_back({A, Cost});  // 순방향 그래프 저장
    }

    // 최단 거리 배열 초기화
    fill(Dist[0], Dist[1] + MAX, INTMAX);

    // 순방향 그래프에서 X로 가는 최단 거리 계산
    Dijkstra(1, X);

    // 역방향 그래프에서 X로 가는 최단 거리 계산
    Dijkstra(0, X);

    // 모든 정점에 대해 순방향과 역방향 최단 거리를 합쳐 최댓값 갱신
    for (int i = 1; i <= N; ++i)
    {
        answer = max(answer, Dist[0][i] + Dist[1][i]);
    }

    cout << answer;

    return 0;
}

두 코드 차이

최적화 풀이 출처

https://hyeo-noo.tistory.com/138

[백준 1238] 파티 C++