[백준] 1238 파티 (파이썬)

골드 Ⅲ

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

1238번: 파티

 

📄 문제

• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
• N명의 학생이 X (1 ≤ X ≤ N) 번 마을에 모여서 파티를 벌이기로 했다.
• 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다.
• 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
• 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다.

 

N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

---

💡 아이디어

1. 아래의 힌트로 다익스트라 알고리즘을 사용하여 최단거리를 구한다.
   • 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti의 시간을 소비한다.
   •  X번 마을에 걸어가서 다시 그들의 마을로 돌아와야 한다.
   • 최단 시간에 오고 가기를 원한다.
2. 각 마을에서 X번 마을까지의 최단시간과 X번 마을에서 각 마을의 최단시간을 더해 최댓값을 구한다.
3. 각 마을에서 X번 마을까지의 최단거리를 구한다. (다익스트라)
   • 처음에 그래프를 입력받을 때, 역방향 그래프도 입력받는다.
     
   • 역방향 그래프에서 X를 시작점으로 설정하면 각 마을에서 X번 마을까지의 최단거리를 알 수 있다. ( dijkstra(x) )
4. X번 마을에서 각 마을의 최단거리를 구한다. (다익스트라)
   • X번 마을을 시작점으로 잡고 다익스트라 함수를 실행하면 각 마을까지의 최단거리가 나온다. ( dijkstra(x) )
   • 다익스트라 함수를 한 번만 실행하면 X번 마을에서 모든 마을의 최단거리가 나온다.

---

 

"3. 각 마을에서 X번 마을까지의 최단거리를 구한다."에 대해 정방향, 역방향 두 가지 풀이 방법이 존재한다.

🟩 첫 번째 아이디어 (정방향) 

• for 문을 활용하여 각 마을을 시작 점으로 잡고 X번 마을까지의 최단거리를 구한다. ( dijkstra(i)[x] )
• 정점이 최대 1000개가 주어진다.
• 최악의 경우에는 다익스트라 함수를 1001번 사용해야 하기 때문에 비효율적이다.

 

 

첫 번째 아이디어를 개선하기 위해 두 번째 아이디어를  사용한다.

✅ 두 번째 아이디어 (역방향) - 최종코드 

• 처음에 그래프를 입력받을 때, 역방향 그래프도 입력받는다.
  
• 역방향 그래프에서 X를 출발점으로 지정하면 각 마을에서 X로 들어오는 길을 따라 이동하게 된다.
• X번 마을을 시작점으로 설정하면 각 마을에서 X번 마을까지의 최단거리를 알 수 있다. 
• 즉, 다익스트라 함수를 한번 사용하여 각 마을에서 X번 마을까지의 최단 거리를  알 수 있다.  ( dijkstra(x) )

 

3. 각 마을에서 X번 마을까지의 최단거리 그림 (정방향 vs 역방향)

 

📝 문제 풀이 (Code)

최종 코드 ( 실행시간 56 ms, 메모리 34348 KB )

import sys, heapq
input = sys.stdin.readline

def dijkstra(start, roadGraph):
    visited = [100001]*(n+1)
    heap = [(0, start)]
    visited[start] = 0

    while heap:
        totalTime, curr = heapq.heappop(heap)

        # 저장된 시간 보다 많으면 탐색 안함
        if visited[curr] < totalTime:
            continue

        for next, nextTime in roadGraph[curr]:
            ssumTime = totalTime + nextTime
            if ssumTime < visited[next]:
                visited[next] = ssumTime
                heapq.heappush(heap, (ssumTime, next))
    return visited


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

graph = [[] for _ in range(n+1)]
reverseGraph = [[] for _ in range(n+1)]

for _ in range(m):
    s,e,t = map(int, input().split())
    # 단방향 도로
    graph[s].append((e,t))
    # 역방향 도로
    reverseGraph[e].append((s,t))

# 가장 오래 걸리는 학생 시간 저장
ans = 0

# x에서 출발하여 각 마을에 도착하는 최단 시간 구하기
startX = dijkstra(x, graph)
# 각 마을에서 x까지 최단 시간 구하기 (역방향을 활용하여 계산)
reverseX = dijkstra(x, reverseGraph)

# 가장 많은 시간을 소비하는 학생 찾기
for i in range(1, n+1):
    if i == x:
        continue
    total = reverseX[i] + startX[i]
    ans = max(ans, total)

print(ans)

---

처음 코드 ( 실행시간 956 ms, 메모리 34348 KB )

최종 코드에 비해 비효율적이다.

(for문을 돌려 각 마을에서 X번 마을까지 최단거리를 일일이 계산한다.)

• 단 방향 그래프를 입력받는다.
• for문을 사용하여 각 마을에서 X번 마을까지의 최단거리를 구한다. ( dijkstra(i)[x] )
• 최악의 경우에는 다익스트라 함수를 1001번 사용해야 한다.

import sys, heapq
input = sys.stdin.readline

def dijkstra(start):
    visited = [100001]*(n+1)
    heap = [(0, start)]
    visited[start] = 0

    while heap:
        totalTime, curr = heapq.heappop(heap)

        # 저장된 시간 보다 많으면 탐색 안할래
        if visited[curr] < totalTime:
            continue

        for next, nextTime in graph[curr]:
            ssumTime = totalTime + nextTime
            if ssumTime < visited[next]:
                visited[next] = ssumTime
                heapq.heappush(heap, (ssumTime, next))
    return visited


n, m, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    s,e,t = map(int, input().split())
    # 단방향 도로
    graph[s].append((e,t))

# 가장 오래 걸리는 학생 시간 저장
ans = 0

# x에서 출발하여 각 마을에 도착하는 최단시간 구하기
startX = dijkstra(x)
# 각 마을에서 x까지 최단시간 구하기
for i in range(1,n+1):
    if i == x:
        continue
    total = dijkstra(i)[x] + startX[i]
    ans = max(ans, total)

print(ans)