[알고리즘] BOJ 1238 파티 #Python

김상현·2023년 2월 4일

알고리즘

목록 보기

276/301

[BOJ] 1238 파티 바로가기

📍 문제

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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

📍 풀이

🧷 풀이 과정

정점간 최단 거리를 구하는 문제는 다익스트라(Dijkstra) 혹은 플로이드 워셜(Floyd Warshall) 알고리즘을 적용하면 된다.
해당 문제에서 놓치면 안되는 중요한 포인트는 주어진 간선(도로)이 단방향 이라는 점, 목적지(X)가 정해져 있다는 점이다.

✏️ 플로이드 워셜

처음 접근한 방식은 모든 학생의 이동 시간을 구해야 한다는 점을 고려하여 플로이드 워셜(Floyd Warshall) 알고리즘을 적용하였지만, 시간 초과 문제가 발생했다.
학생의 수(N)가 최대 1000명이라는 점을 고려하면 1000 * 1000 * 1000 의 시간 복잡도가 발생하기 때문에 해당 알고리즘은 적용할 수 없음을 알 수 있다.

✏️ 다익스트라

다음으로 접근한 방식은 다익스트라(Dijkstra) 알고리즘이다.

마을(I)에서 목적지(X)로 이동하는 최단 시간을 다익스트라 알고리즘으로 구한다.

def findMinIToX(i):
    itoXGraph = [maxsize] * (N+1)
    itoXGraph[i] = 0
    heap = [(0,i)]
    while heap:
        w, node = heappop(heap)
        if node == X: continue
        for nextNode, weight in graph[node]:
            if itoXGraph[nextNode] > w + weight:
                itoXGraph[nextNode] = w + weight
                heappush(heap, (w+weight, nextNode))
    
    return itoXGraph[X]

목적지(X)에서 다른 마을(I)로 이동하는 최단 시간을 다익스트라 알고리즘으로 구한다.

def createXToIGraph():
    xToIGraph = [maxsize] * (N+1)
    xToIGraph[X] = 0
    heap = [(0,X)]
    while heap:
        w, node = heappop(heap)
        for nextNode, weight in graph[node]:
            if xToIGraph[nextNode] > w + weight:
                xToIGraph[nextNode] = w + weight
                heappush(heap, (w+weight, nextNode))
    return xToIGraph

마을(I)에서 목적지(X)로, 목적지(X)에서 마을(I)로 이동하는 시간을 더한 후 가장 긴 시간이 걸리는 학생의 이동 시간을 반환한다.

for i in range(1, N+1):
    if i == X: continue
    # (X → I → X) 최장 시간 갱신
    answer = max(answer, xToIGraph[i] + findMinIToX(i)) 

return answer

✍ 코드

# BOJ 1238 파티
# https://www.acmicpc.net/problem/1238

from sys import stdin, maxsize
from heapq import heappop, heappush
from collections import defaultdict

def solution1(N, X, edges):
    answer = 0

    # 마을 간 이동 시간 list → defaultdict
    graph = defaultdict(list)
    for s, e, w in edges:
        graph[s].append((e,w))

    # X → I 이동 최단 시간
    def createXToIGraph():
        xToIGraph = [maxsize] * (N+1)
        xToIGraph[X] = 0
        heap = [(0,X)]
        while heap:
            w, node = heappop(heap)
            for nextNode, weight in graph[node]:
                if xToIGraph[nextNode] > w + weight:
                    xToIGraph[nextNode] = w + weight
                    heappush(heap, (w+weight, nextNode))
        return xToIGraph
    
    # I → X 이동 최단 시간
    def findMinIToX(i):
        itoXGraph = [maxsize] * (N+1)
        itoXGraph[i] = 0
        heap = [(0,i)]
        while heap:
            w, node = heappop(heap)
            if node == X: continue
            for nextNode, weight in graph[node]:
                if itoXGraph[nextNode] > w + weight:
                    itoXGraph[nextNode] = w + weight
                    heappush(heap, (w+weight, nextNode))
        
        return itoXGraph[X]

    xToIGraph = createXToIGraph()
    
    for i in range(1, N+1):
        if i == X: continue
        # (X → I → X) 최장 시간 갱신
        answer = max(answer, xToIGraph[i] + findMinIToX(i)) 

    return answer

# input
N, M, X = map(int,stdin.readline().split())
edges = [list(map(int,stdin.readline().split())) for _ in range(M)]

# response
res = solution1(N, X, edges)
print(res)