[Python/백준] 1238. 파티

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

다익스트라 알고리즘

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

---

현장에서 모의고사로 푼 풀이

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

# n개의 숫자로 구분
# 정점 N개(1~n), m개의 단방향 도로
# i번쨰 길을 지나는 데 T[i]의 시간이 소비됨.

# 입력 : n, m, x
# x에 갔다가 집에 와야함
# 그 다음부터는 x -> y 가는 데 t 걸리는 간선정보 들어옴

# 이거, 각 학생이 target까지 가는 시간과, 돌아오는 시간을 구해야 함.
# => 다익스트라를 두 번 써서 학생 -> target, target -> 학생 구한 다음에,
# 이걸 학생 수만큼(n번) 써서 그 중에 max 고르면 됨.

def dijkstra(node):
    # 다익스트라 시작 정점 초기화
    distances[node] = 0
    heap = [(distances[node], node)]

    # 힙 빌 때까지 반복
    while heap:
        min_dist, node = heappop(heap)

        if min_dist > distances[node]:
            continue

        # 여기서 중요한데...
        for dist, next_node in graph[node]:
            next_dist = min_dist + dist
            if next_dist < distances[next_node]:
                distances[next_node] = next_dist
                heappush(heap, (next_dist, next_node))

n, m, target = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a].append((t, b))

INF = float('inf')


max_time = 0
for student in range(n+1):
    distances = [INF] * (n + 1)
    dijkstra(student)
    cur_time = distances[target]
    distances = [INF] * (n + 1)
    dijkstra(target)
    # print(f'student {student}의 가는 거리와 오는 거리는, 각각')
    # print(f'{cur_time}, {distances[student]} 입니다.')
    cur_time += distances[student]

    if cur_time != INF:
        max_time = max(max_time, cur_time)

print(max_time)

다익스트라는, '내가 고정관념을 꺠뜨려야 하나?'를 생각해보면 좋음

특히, “내가 꼭 정직하게 출발해야 할까? 오히려 이상한 데에서 출발하는 게 정답 아닐까? 도착 정점에서 시작하면 안될까?”, “그래프를 뒤집으면 안될까?” 같은, 틀을 깨는 생각을 할 수 있어야 함.

이것도 결국 경험치.

---

집와서 다시 풀어본 풀이