[백준 1753번] 파이썬 - 최단 경로

http://www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

# 조건

• 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램 작성
• 모든 간선의 가중치는 10 이하이다.

 

# 입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)

• 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.
• 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.
• 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다.
  • 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다.
  • u와 v는 서로 다르며 w는 10 이하의 자연수이다.
  • 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

# 접근 방법 및 Solution

• 시작점은 0으로, 경로가 존재하지 않는 경우에는 INF를 출력한다.
• heapq를 이용하여 가중치에 따라 리스트에 담아주고, 가중치가 작은 경로를 따라 이동한다.
• BFS를 이용하여 시작 정점에서 모든 정점까지의 VISITED 배열에 최단 경로를 기록해준다.

 

# 시간초과

• 정점의 수 20,000개, 간선의 수 30,0000개 이하라 그런지 시간 초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  
  
def BFS(start):                         # 시작 정점 인자로 받기  
    global graph  
    visited = [float('INF')] * (V+1)    # 최단 경로 위해 INF로 방문리스트 만들기  
    visited[0], visited[start] = 0, 0   # 존재하지 않는 0번 정점과, 시작 정점은 0  
    q = []  
    heappush(q, (start, 0))             # 출발 정점과 누적 가중치 push  
    while q:  
        cur_node, cur_dist = heappop(q)  
        for node, dist in graph[cur_node]:  
            if visited[node] > dist + cur_dist:  
                visited[node] = dist+cur_dist  
                heappush(q, (node, dist+cur_dist))  
    print(*[visited[i] if visited[i] != float('inf') else 'INF' for i in range(1, len(visited))], sep='\n')  
  
V, E = map(int, input().split())        # 정점의 개수 V와 간선의 개수 E  
K = int(input())                        # 시작 정점의 번호  
  
graph = [[] for _ in range(V+1)]  
  
for _ in range(E):  
    u, v, w = map(int, input().split())  
    graph[u].append((v, w))  
  
BFS(K)

 

# pass 풀이

• heapq에 가중치와 출발 노드를 넣어줄 때, 순서를 반대로 넣어주었다.
• 가중치가 아닌 출발 노드가 최소힙으로 구성되어 시간초과가 발생했던 것..
• 항상 heapq를 사용할 때는 꼭 넣는 순서를 잘 지켜주자.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  
  
def BFS(start):                         # 시작 정점 인자로 받기  
    global graph  
    visited = [float('INF')] * (V+1)    # 최단 경로 위해 INF로 방문리스트 만들기  
    visited[0], visited[start] = 0, 0   # 존재하지 않는 0번 정점과, 시작 정점은 0  
    q = []  
  
    heappush(q, (0, start))             # 누적 가중dhk 출발 정점  push  
  
    while q:  
        cur_dist, cur_node = heappop(q)  
        if visited[cur_node] < cur_dist:  
            continue  
  
        for node, dist in graph[cur_node]:  
            d = dist+cur_dist  
            if visited[node] > d:  
                visited[node] = d  
                heappush(q, (d, node))  
  
    for i in range(1, len(visited)):  
        print(visited[i] if visited[i] != float('inf') else 'INF')  
  
  
V, E = map(int, input().split())        # 정점의 개수 V와 간선의 개수 E  
K = int(input())                        # 시작 정점의 번호  
  
graph = [[] for _ in range(V+1)]  
  
for _ in range(E):  
    u, v, w = map(int, input().split())  
    graph[u].append((v, w))  
  
BFS(K)