8주차 스터디 그래프 이론 - 백준 1238번 파티

www.acmicpc.net/problem/1238

1238번: 파티

IDEA

N개의 정점에서 파티가 열리는 특정한 X점까지 갔다가 다시 돌아오는 최소 시간을 물어보는 문제다. 

이것도 다익스트라를 이용해서 풀었다. 뭐 플로이드 와샬을 이용해서 풀어도 될 거 같다.

 

만약, 문제가 양방향이라면 정점 -> 파티장 비용과 파티장 -> 정점의 비용이 같으므로 시작지점을 파티장으로 설정한 후 다익스트라를 이용하면 된다. 

하지만, 이 문제는 도로가 단방향이기때문에 정점 -> 파티장 비용과 파티장 -> 정점 비용이 다르다.

그럼 어떤 점을 시작지점으로 두어야할까?

다익스트라는 한 정점에서 모든 정점까지의 최소비용을 구하는 알고리즘 아닌가? 

맞다. 근데 그 한 정점을 1~n번까지 돌아가며 적용해주면 모든 정점 ~ 모든 정점까지의 최소비용을 구할 수 있다. 

핵심 아이디어는 n개의 점을 시작지점으로 설정한 후, 다익스트라 알고리즘을 사용하는 것이다. 

다익스트라의 시간복잡도가 ElogV라면 이 문제는 다익스트라를 v번 반복해야하므로 VElogV이다.

이 문제에서 정점은 1000개, 간선은 10000개라고 했으니 시간은 충분하다. 

 

cost[i][j] : 시작지점이 i일 때, j까지 가는 최소비용 이라는 뜻으로 cost 배열을 2차원으로 설정했다.

i 는 1부터 n까지 반복문을 돌며 

시작지점을 i로 설정하며 cost[i][i]는 무조건 0이고, 나머지 점들까지의 cost는 inf이다.

i점부터 시작해 다른 점들까지의 최소비용을 업데이트하며 cost[i][]를 채운다. 

반복문이 끝나면 1~n까지  정점 -> 파티장 비용과 파티장 -> 정점의 비용의 합을 구하고

그 중 최댓값을 반환해준다. 

 

CODE - C++

#include <iostream>
#include <vector>
#include<algorithm>
#include<queue>
#include<string.h>

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; //거리 , 인덱스

vector<vector<pair<int, int>>> graph; 

int cost[1005][1005] = { 0 };
bool visited[1005][1005]= { false };

int n, m, party; // 정점의 개수 , 입력의 개수 

void dijkstra(int start) {
    q.push({ 0 , start });
    visited[start][start] = true;

    while (!q.empty()) {
        int cur = q.top().second;
        q.pop();
        visited[start][cur] = true;

        for (int i = 0; i < graph[cur].size(); i++) {
            int new_s = graph[cur][i].first;
            int new_c = graph[cur][i].second;
          //  printf("%d->%d : %d -> %d\n", cur, new_s, cost[start][new_s], cost[start][cur] + new_c);
            //cost 업데이트
            if (cost[start][cur] + new_c < cost[start][new_s]) {
                cost[start][new_s] = cost[start][cur] + new_c;
                if (!visited[start][new_s]) q.push({ cost[start][new_s] , new_s });
            }
        }
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> party;
   
    graph.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({ b, c });
    }
    //i: 시작점 , cost[i] = 0 나머지 fill  
    memset(cost, 999999, sizeof(cost));

    for (int start= 1; start <= n; start++) {
        cost[start][start] = 0; //시작점의 cost = 0
        //시작점 -> 다른 점 의 cost를 구해주자.
        dijkstra(start);
    }

    int  nmax = 0;
    for (int i = 1; i <= n; i++) {
        if (i == party) continue;
        nmax = max(nmax, cost[party][i] + cost[i][party]);
    }
    printf("%d" , nmax);
}

CODE - Python

import sys
input = sys.stdin.readline

from heapq import heappush , heappop

# 정점, 간선 , 파티장소
n,m,party = map(int, input().split()) 
graph = [[]for _ in range(n+1)]
cost = [[987654321 for _ in range(n+1)] for _ in range(n+1)]
#cost[i][j] : 시작지점이 i일 때, j까지의 최소비용

for i in range(m):
  start , end , time = map(int,input().split())
  graph[start].append([time , end]) 

def dijkstra():
  for start in range(1,n+1):
    # 시작지점 start  : start ~ 다른 정점 살펴봄 
    cost[start][start] = 0
    heap = []
    heappush(heap, [0,start])
    while heap:
      cur_cost , cur_node =  heappop(heap)
      for time , next_node in graph[cur_node]:
        if (cost[start][next_node] > time + cur_cost) :
          cost[start][next_node] = time + cur_cost
          heappush(heap,[cost[start][next_node] , next_node])


def cal_min_distance():
  nmax = 0
  for start in range(1,n+1):
    dist = cost[party][start] + cost[start][party]
    nmax = max(nmax , dist)
  return nmax


dijkstra()
print(cal_min_distance())