[백준 / 1238] 파티 - Python

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

1238번: 파티

<접근>

N과 목적지 X가 있다고 하면 N -> X -> N의 최단 거리를 구하면 된다. 전체 노드로부터 목적지 X까지의 최단거리와 X에서 전체 노드까지의 거리를 '다익스트라 알고리즘'을 통하여 구해 비교해준다.

 

따라서 다익스트라 알고리즘을 선행해야 한다.

 

2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

[보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

<입력>

N, M, X = map(int, input().split())

graph = {i+1: {} for i in range(N)}

for _ in range(M):
    x, y, v = map(int, input().split())
    graph[x][y] = v

 

전체 마을의 개수 N과 경로의 개수 M과 목적지 X를 입력받는다. 

 

전체 노드의 개수 N개 만큼 마을의 경로를 추가하기 위해서 딕셔너리 형태로 각 Key를 선언해준다.

 

경로의 개수 M만큼 단방향 그래프를 그려준다. x -> y로 가는 v 시간만큼의 길을 { x1 : { y1 : v1, y2 : v2... }, x2 :... }의 형태의 그래프로 그려준다. 문제에서 경로는 1개이므로 같은 경로가 2번 입력되지 않는다.

 

<알고리즘 1>

import heapq


def dijkstra(graph, start):
    distances = {i: float('inf') for i in graph}
    distances[start] = 0

    queue = [[0, start]]

 

알고리즘의 시간을 줄여주기 위해서 heapq를 import 한다.

 

함수는 graph와 start지점을 입력받는다.

최단 거리를 구하는 알고리즘이므로 시작 지점으로부터 각각의 거리가 계산될 거리의 처음 값을 최대수인 'inf'로 설정해준다. 그리고 시작 지점의 처음 값은 0이므로 0으로 설정해준다.

 

queue에 현재까지의 거리와 출발 노드(마을)를 넣는다.

<알고리즘 2>

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for new_node, new_distance in graph[current_node].items():
            distance = current_distance+new_distance

            if distance < distances[new_node]:
                distances[new_node] = distance
                heapq.heappush(queue, [distance, new_node])

    return distances

 

queue가 있는 동안 반복한다.

queue에서 현재 거리와 현재 노드를 받아온다. 만약 현재의 거리가 distances에 저장된 거리보다 크면 해당 값들은 무시하고 다음 값을 queue에서 받아오게 한다.

 

graph에서 현재 노드와 연결된 노드와 거리를 받아오고, 연결된 노드로 가는 시간인 현재시간과 노드와의 거리를 더해준다. 만약 distances의 값보다 작은 경우, 해당 값을 경신하고, 해당 거리와 노드(마을)를 queue에 넣는다. 

 

해당 작업이 끝나면 distances를 반환해준다.

<연산 및 출력>

from_X_to = dijkstra(graph, X)

maxTime = 0
for i in graph:
    time = from_X_to[i]+dijkstra(graph, i)[X]
    if maxTime < time:
        maxTime = time

print(maxTime)

 

먼저 목적지 X로 부터 돌아오는 모든 노드의 거리를 계산한다.

 

그래프에 있는 모든 마을을 돌면서 돌아오는 거리와 목적지까지 가는 거리를 더해서 time에 넣는다. 만약 time이 maxTime의 값보다 크다면 해당 값을 갱신해주고 최대 값을 찾아서 출력해준다.

<전체 코드>

import heapq


def dijkstra(graph, start):
    distances = {i: float('inf') for i in graph}
    distances[start] = 0

    queue = [[0, start]]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for new_node, new_distance in graph[current_node].items():
            distance = current_distance+new_distance

            if distance < distances[new_node]:
                distances[new_node] = distance
                heapq.heappush(queue, [distance, new_node])

    return distances


N, M, X = map(int, input().split())

graph = {i+1: {} for i in range(N)}

for _ in range(M):
    x, y, v = map(int, input().split())
    graph[x][y] = v

from_X_to = dijkstra(graph, X)

maxTime = 0
for i in graph:
    time = from_X_to[i]+dijkstra(graph, i)[X]
    if maxTime < time:
        maxTime = time

print(maxTime)