백준 1238 [파티] 파이썬

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

 

# 백준 1238 파티
# N개의 마을, M개의 단방향 도로, 파티 장소 X
# 각 학생이 자기 마을에서 X로 갔다가 다시 자기 마을로 돌아오는 데 걸리는
# 왕복 최단 시간 중 최댓값을 구하는 문제

import sys, heapq

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

# dist[i][j] = i에서 j까지의 최단 거리
dist = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
# costs[u] = (가중치, v) 형식으로 u → v 간선 저장
costs = [[] for _ in range(N+1)]

# 도로 정보 입력
for _ in range(M):
    A, B, cost = map(int, input().split())
    costs[A].append((cost, B))

# 다익스트라 함수: start에서 다른 모든 노드까지 최단 거리 계산
def dijkstra(start):
    dist[start][start] = 0   # 자기 자신까지의 거리는 0
    q = []
    heapq.heappush(q, (0, start))  # (누적 비용, 현재 노드)

    while q:
        cost, curr = heapq.heappop(q)
        # 이미 더 짧은 거리로 방문한 적 있으면 무시
        if dist[start][curr] < cost:
            continue
        # 인접 노드 확인
        for next_cost, nxt in costs[curr]:
            new_dist = dist[start][curr] + next_cost
            # 더 짧은 경로 발견 시 갱신 (Relaxation)
            if new_dist < dist[start][nxt]:
                dist[start][nxt] = new_dist
                heapq.heappush(q, (new_dist, nxt))

# 모든 노드에서 출발하는 다익스트라 실행
for i in range(1, N+1):
    dijkstra(i)

# 정답 계산
# i번째 학생이 X로 가는 최단거리(dist[i][X]) + 돌아오는 최단거리(dist[X][i])
# 그 중 최댓값
ans = 0
for i in range(1, N+1):
    ans = max(dist[X][i] + dist[i][X], ans)

print(ans)

시간복잡도와 공간복잡도를 고려했을때, i번째집->파티장->i번째집으로 이동하는 경로를 구하기위해 다익스트라를 N번해도 문제가없을거라 생각해서 다익스트라를 N번 돌렸다. 통과했다.

 

하지만, GPT가 역방향 다익스트라를 제시했고 이는 다익스트라 2번으로 해결된다.

 

import sys, heapq

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

# 원래 그래프와 역방향 그래프를 저장할 인접 리스트
graph = [[] for _ in range(N + 1)]
rev_graph = [[] for _ in range(N + 1)]

# 그래프 입력 받기 (원래 그래프와 역방향 그래프 동시 생성)
for _ in range(M):
    A, B, cost = map(int, input().split())
    graph[A].append((cost, B))
    rev_graph[B].append((cost, A))

def dijkstra(start, adj_list):
    dist = [float('inf')] * (N + 1)
    dist[start] = 0
    q = [(0, start)]

    while q:
        cost, curr = heapq.heappop(q)
        if dist[curr] < cost:
            continue
        for next_cost, next_node in adj_list[curr]:
            new_dist = cost + next_cost
            if new_dist < dist[next_node]:
                dist[next_node] = new_dist
                heapq.heappush(q, (new_dist, next_node))
    return dist

# 1. 파티장에서 각 학생의 집으로 돌아가는 최단 거리 (X -> i)
dist_to_home = dijkstra(X, graph)

# 2. 각 학생의 집에서 파티장으로 가는 최단 거리 (i -> X)
#    이는 역방향 그래프에서 X를 시작점으로 하는 최단 거리와 동일
dist_to_party = dijkstra(X, rev_graph)

ans = 0
for i in range(1, N + 1):
    total_dist = dist_to_home[i] + dist_to_party[i]
    ans = max(ans, total_dist)

print(ans)

1. 파티장 -> i번째 집 이동

  -이는 기존과 같이 다익스트라를 이용하여 구하면 된다. 

 

2. i번째 집 -> 파티장 이동

  - 우리가 궁금한 것은 i번째 집에서 파티장까지 이동하는 최소 거리이다. 반대로 생각하면 파티장에서 i번째 집까지 이동한다고 생각하고, 단방향 그래프를 뒤집어서 다익스트라를 이용할 수 있다.

 

열심히 해보자..