백준 1238 파티 c++ [컴공과고씨]

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

1238번: 파티

다익스트라 알고리즘을 활용한 문제로 bfs를 이용해도 가능하지만 시간 측면으로 볼때 다익스트라가 더 빠르고 나중에 다른 문제를 풀 때 다익스트라로 풀지않고 bfs로 풀면 시간 초과가 걸리는 문제들이 많기 때문에 최단 경로 문제 같은 경우 다익스트라로 풀어주는게 좋다. 다익스트라 알고리즘는 https://hagisilecoding.tistory.com/134 여기서 살펴보고 오면 이 문제를 쉽게 이해할 수 있다.

 

문제 간단 설명

n명의 학생이 파티를 해서 x번 학생 집에 모이기로 함.

각 집과 집을 잇는 도로가 있고 이 도로들을 이용해서 학생들이 x번 학생 집까지 최단거리로 다녀간다고 함.

x번 학생의 집까지 오고 가는 거리가 가장 긴 학생의 거리를 찾는 문제.

이 때 오고 가는 길은 단방향임.

 

문제 해결 방법

다익스트라 알고리즘을 사용하여 각각의 학생들의 x 학생집까지의 거리와 x 학생집에서 자신의 집까지의 거리를 구하고

두 거리를 합 한 후 가장 긴 학생의 거리를 찾아준다.

위 다익스트라 알고리즘 포스터를 보고 전체 코드를 보면 이해하기 쉬움.

 

전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define INF 98765432
using namespace std;
int n,x,m;
vector<pair<int, int>> v[1002];
int dst[1002]; // 정점까지의 최단거리를 기록
int result; // 최단거리
 
// 다익스트라
void fc(int a, int d){
    memset(dst, INF, sizeof(dst)); // 초기값 INF
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 우선순위 큐(최소 거리가 루트로)
    pq.push({0, a});// pq(거리, 정점)
    dst[a] = 0; // 시작 지점 거리 0으로 초기화
    while(!pq.empty()){
        int cx = pq.top().second; // 현재 정점
        int cdst = pq.top().first; // 현재 정점까지 거리
        pq.pop();
        if(cx == d){ // 현재 정점에 도착했다면
            result = dst[cx]; // 최단 거리 기록
            break;
        }
        for (int i = 0; i < v[cx].size();i++){ 
            // 현재 정점과 이어진 다음 정점들 
            int nx = v[cx][i].first; // 다음 정점 
            int ndst = v[cx][i].second + cdst; // 다음 정점까지 거리 계산
            if(dst[nx] > ndst){
                 // 다음 정점까지 거리와 기록된 정점까지 거리와 비교해
                 // 최단거리라면
                dst[nx] = ndst; // 최단거리 기록
                pq.push({ndst, nx}); // 큐에 넣어줌
            }
        }
    }
}
int main(){
    cin >> n >> m >> x;
    int ans1, ans2, ans;
    ans = 0;
    int a, b, t;
    for (int i = 0; i < m;i++){
        cin >> a >> b >> t;
        v[a].push_back({b, t});
    }
    for (int i = 1; i <= n;i++){
        fc(i, x); // 가는 길 최단 거리 
        ans1 = result; 
        fc(x, i); // 오는 길 최단 거리
        ans2 = result;
        if(ans < ans1+ans2)
            ans = ans1 + ans2; // 합
    }
    cout << ans << '\n'; // 최단 거리 출력
    return 0;
}