백준 1238번 [파티](C++) -yes6686- 티스토리

백준 문제 풀이: 1238 [파티]

---

문제 링크: https://www.acmicpc.net/problem/1238

문제 설명:

각 마을에서 특정 마을 X로 가는 최단 시간과, X에서 각 마을로 돌아오는 최단 시간을 모두 계산하여 왕복 시간이 가장 오래 걸리는 학생의 왕복 시간을 구하는 문제입니다.

입력:

• 첫째 줄에 마을의 수 n, 도로의 수 m, 파티가 열리는 마을 번호 X가 주어집니다. (1 ≤ n ≤ 1,000, 1 ≤ m ≤ 10,000)
• 둘째 줄부터 m개의 줄에 도로 정보가 주어집니다. 각 줄은 세 정수 a, b, cost로 구성되며, 이는 a번 마을에서 b번 마을로 가는 비용이 cost임을 의미합니다.

출력:

• 가장 오래 걸리는 학생의 왕복 시간을 출력합니다.

예시:

입력:
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

출력:
10

---

문제 해결 코드

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

const int INF = 1e9;

vector<pair<int, int>> graph[1001]; // 그래프 인접 리스트
int dist[1001]; // 최단 거리 배열

void dijkstra(int start, int n) {
    priority_queue<pair<int, int>> pq;
    fill(dist, dist + n + 1, INF); // 최단 거리 초기화
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if (cost > dist[cur]) continue;

        for (auto &edge : graph[cur]) {
            int next = edge.first;
            int nextCost = edge.second;

            if (dist[next] > cost + nextCost) {
                dist[next] = cost + nextCost;
                pq.push({-dist[next], next});
            }
        }
    }
}

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

    int n, m, x;
    cin >> n >> m >> x;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }

    int maxTime = 0;

    // 1. X에서 각 마을로의 최단 거리 계산
    dijkstra(x, n);
    vector<int> distFromX(n + 1);
    for (int i = 1; i <= n; i++) {
        distFromX[i] = dist[i];
    }

    // 2. 각 마을에서 X로의 최단 거리 계산
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        dijkstra(i, n);
        maxTime = max(maxTime, dist[x] + distFromX[i]);
    }

    cout << maxTime << '\n';
    return 0;
}

---

코드 설명

이 코드는 다익스트라 알고리즘을 두 번 사용하여 왕복 시간을 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 다익스트라 알고리즘으로 각 마을에서 다른 마을까지의 최단 거리를 계산합니다.
  • X에서 각 마을로의 최단 거리와 각 마을에서 X로의 최단 거리를 합산하여 왕복 시간을 구합니다.
• 구현 세부사항:
  • graph[a].push_back({b, c}): 마을 a에서 b로 가는 비용 c를 그래프에 저장합니다.
  • dist: 현재 시작점에서 다른 마을까지의 최단 거리를 저장합니다.
  • 왕복 시간 계산: distFromX[i] + dist[x] 중 최댓값을 구합니다.
• 시간 복잡도 분석:
  • 다익스트라 알고리즘: O((n + m) log n)
  • n번 다익스트라 실행: O(n * (n + m) log n)
  • 전체 시간 복잡도: O(n * (n + m) log n)

---

결과

코드는 입력된 그래프에서 왕복 시간이 가장 오래 걸리는 학생의 왕복 시간을 계산하여 출력합니다. 다익스트라 알고리즘을 사용하여 효율적으로 문제를 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!