[Python] 백준 1753 최단경로

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

 

문제 분석

• 방향 그래프가 주어졌을 때
• 주어진 시작 시점에서 다른 모든 정점으로의 최단 경로를 구하라

• v : 정점의 개수, e : 간선의 개수
• 모든 정점에 1~v까지의 번호가 있음

• s : 정점 시작번호

• e개의 각 간선을 나타내는 세개의 정수 (u, v, w)
• u에서 v로 가는 (방향이 있음)
• 가중치 w인 간선이 존재

• 서로 다른 두 정점 사이에 여러개의 간선이 존재할 수도 있다.

• K에서 각 정점으로 가는 최단거리 출력
• 자기 자신이면 0
• 경로가 없으면 'INF' 출력

 

코드 설계

1차

• BFS ?
• 시작 정점 K → 도착 위치이면 거리 return
• 처음이 작다고 최단거리가 될거라는 보장이 없으니 모든 경우의 수를 구해야 할 듯 (완탐?)
• 모든 도착 지점에 대한 도착 횟수를 리스트에 저장
• 마지막에 다 끝나면 min(list)

• 맨 처음 1~v  까지 돌면서 도착지점 확인
  • 모든 리스트를 다 돌건데, 만약 이전에 갔던 간선이면 또 가지 x (모든 경우의 수를 확인할 것이기 때문에 다른 경우에 수에서 체크될 것)
    • 어떻게 모든 경우의 수 체크?
  • 현재 위치는 시작점
  • 간선 리스트를 하나씩 돌면서 만약 현재 시작점인 값이 있으면

 

2차

1. 도착한 것을 어떻게 확인할 것인가

• 현 위치와 도착하려는 위치가 같으면 도착

2. 어떻게 최단 거리를 찾을 것인가

• 현재 위치에서 시작하고 end_point 에서 끝나는 값이 있는지 확인
  • 그런 값이 여러개라면 w가 가장 작은거
• 없으면
  • 이동할 수 있는 모든 거리 추적
  • 시작과 도착이 같으면 w 작은거 선정

3. 어떻게 경로가 존재하지 않음을 확인하는가

• 더 이상 나아갈 수 없을 때 (나의 현재 위치에서 시작할 수 있는 리스트 값이 없을 때)

 

정답 코드

1차.. 실패.. 엉망진창

import sys
input = sys.stdin.readline
from collections import deque

V, E = map(int, input().split())
start = int(input())
move = deque()

for i in range(E) :
    move.append(list(map(int, input().split())))

distance = []

for end in range(1, V+1) : # 도착지점 1~v
    print('end : ', end)
    dis = 0
    if end == start:
        print(0)
        continue
        
    current = start
    while move : # 모든 간선 확인
        u,v,w = move.popleft()
        if end in (u,v) :
            if current in (u, v):  # start와 다른 값을 현재 위치로 이동하고
                if u == current:
                    current = v
                else:
                    current = u
                dis += w
            distance.append(dis) # todo 이러면 아직 한 경우의 수만 탐색하는 건데..

        else :
            move.append((u,v,w))
            continue


    print(min(distance))

 

실패.. 

다익스트라 알고리즘

 

다른 사람 풀이 1
출처 : https://jie0025.tistory.com/199

다익스트라의 기본

• 다익스트라는 heapq를 이용하면 빠르다.
• 최단 거리 테이블
• 연결 정보

코드 설계

1. u 에서 v로 가는 일방향그래프이기 때문에 graph = [[] for _ in range(V+1) ] 노드의 개수만큼 2차원 리스트를 만든 다음, graph[u].append() 를 해주고, 노드번호와 가중치를 함께 묶어서 입력
2. 최단 거리 테이블 생성 (노드의 개수 V+1 만큼 → V+1은 노드 번호가 1부터 시작되기 때문)
3. 최단거리를 확인하기 위해 INF = int(1e9)라는 변수를 생성, 최단거리일 경우 업데이트

다익스트라 (시작 노드 번호)

1. import heapq
2. hapq를 사용하기 위해 q = [ ] 리스트 생성
3. heapq.heappush( q, value )
   value 부분에 시작노드이므로 거리는 (0, 시작노드번호)를 함께 묶어서 힙큐에 넣어준다.
4. 최단거리테이블[시작노드] = 0 으로 초기화
5. q가 빌때까지 반복
   - heapq.heappop(q) : 큐에서 거리(dist), 노드번호(now)를 꺼낸다.
   - 만약에 꺼낸 거리값이 최단거리테이블( distance[꺼낸 노드번호] ) 에 기록된 정보보다 값이 크면, 최단거리 정보가 아니기 때문에 continue 로 무시한다.
   - 그게 아니라면 최단거리 정보이므로 다음과 같은 작업을 수행한다.
   - for i in graph[꺼낸노드번호]:
   - 꺼낸노드번호에서 갈수 있는 노드와 거리정보를 i를 통해 한개씩 접근
     → i[0] : 현재 노드에서 갈 수 있는 노드 번호
     → i[1] : 현재 노드에서 갈 수 있는 노드 번호까지의 거리

i[0]까지의 최소비용(cost)은 >>> 현재 노드의 최소비용(dist) + i[1]  이다. 만약에 cost값이 최단 거리 테이블의 거리 정보보다 작으면, 업데이트 해주고 힙큐에 정보를 넣어준다. 

이 과정을 반복하면 방문할 수 있는 노드에 대하여 최단거리테이블이 모두 갱신된다.

다익스트라 함수가 끝나면 최단 거리 테이블이 모두 갱신되어있으므로 각 i번쨰 노드까지의 거리는 최단거리테이블의 정보를 출력해주면된다.

만약 방문하지 못한 노드는 INF(1e9)가 그대로 남아 있을테니 확인후 "INF"를 출력한다.

for i in range(1,V+1):

  if distance[i] == INF:

    print("INF")

  else: print(distance[i])

 

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
    q= []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        #현재 노드와 연결된 인접 노드 확인
        for i in graph[now]:
            cost =dist+ i[1]
            if cost < distance[i[0]] :
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))


#V == 5일 때 1~5까지 노드가 있는거임.
V, E = map(int,input().split())

snode = int(input()) #시작 노드

graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1) #최단 거리 테이블
#연결 정보 입력
for _ in range(E):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))


dijkstra(snode)

#i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
for i in range(1,V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

 

 

2회차 - 25.03.31

실패..

import sys
input = sys.stdin.readline
from collections import deque

v, e = map(int, input().split())
# v - 정점의 번호 : 1~v
start_v = int(input())
# 시작점에서 각 정점까지의 최단거리
edge = [[0,0] for _ in range(v)]
visited = [False for _ in range(v)]

for _ in range(e) :
    a,b,w = map(int, input().split())
    edge[a][b] = edge[b][a] = w

d = deque()
d.append((start_v, 0))
visited[start_v] = True

while d :
    cur_v, dis = d.popleft()

    # 경로가 존재하지 않는다면 ('inf')

    # 각 정점에 대한 최단거리? -> 어떻게?
    # 있는 간선 중 가장 작은 가중치를 가지는 값 (그리디)

    # 시작 점에 대해 다음 모든 정점을 갈 수 있는 모든 경우 확인?
    # 해당 경우에 대해 최단 거리 찾기

    for i in range(v) :
        if edge[i][cur_v] :
            d.append((i, dis+edge[i][cur_v]))
            visited[i] = True

 

해설

• 가중치가 있기 때문에 u -> v로 가는 일방향 그래프
• 정점은 1부터 v : (v+1)

import sys, heapq
input = sys.stdin.readline

INF = int(1e9)

def dijkstra(start) :
    hq = []
    # 시작노드로 가기 위한 최단 경로는 0
    heapq.heappush(hq, (0, start))
    distance[start] = 0

    while hq :
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(hq)

        # 꺼낸 값이 최단거리 테이블 (distance)에 기록된 정보보다 값이 크다면, 최단거리 정보가 아니기때뭉네 무시
        if distance[now] < dist :
            continue

        # 현재 노드와 인접한 노드들 확인
        # i[0] : 현재 노드에서 갈 수 있는 노드 번호
        # i[1] : 가중치
        for i in graph[now] :
            cost = dist + i[1]
            if cost < distance[i[0]] :
                distance[i[0]] = cost 
                heapq.heappush(hq, (cost, i[0]))

V, E = map(int, input().split())
start_node = int(input())
graph = [[] for _ in range(V+1)]
# 최단 거리 테이블을 무한으로 초기화
distance = [INF] * (V+1)

# 간선 정보 입력
for _ in range(E) :
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

dijkstra(start_node)

for i in range(1, V+1) :
    if distance[i] == INF :
        print("INF")
    else :
        print(distance[i])

 

 

3회차 - 25.04.03

1차 - 예시 통과, 틀림

import sys, heapq
input = sys.stdin.readline

V, E = map(int, input().split())
s_node = int(input())
INF = 100000 # 모든 간선의 가중치는 10이하의 자연수이다.

# 시작노드에서 각 노드에 대해 최소 거리를 저장할 리스트
distance = [INF for _ in range(V+1)] # 최단 거리를 구하는 거니까 다 큰 값으로 설정

# 노드는 1번부터 V까지 방문 여부 확인
visited = [False for _ in range(V+1)]

g = [[] for _ in range(V+1)] # idx 노드에 대해 [연결노드, 가중치]
for _ in range(E) :
    u, v, w = map(int, input().split())
    # g[u] = [v,w] # 하나만 연결된게 아닐수도 있으니 append
    g[u].append([v,w])

hq = []
heapq.heappush(hq, (s_node, 0))
visited[s_node] = True
distance[s_node] = 0 # 시작노드에서 시작 노드까지의 (최소)거리는 0

while hq :
    # 현재 노드, 거리
    now_node, dis = heapq.heappop(hq) # 최단거리를 알아서 먼저 pop

    # 현재 노드에 대해 연결된 노드들의 최단 거리 업데이트
    # g[now_node] 개수 -> 길이만큼 검사 : 연결된 노드에 대해서 최단거리 업데이트
    # 현재 노드와 연결된 노드들의 거리가 이전 보다 짧으면 update
    # 그 중 아직 방문하지 않은 노드는 heap_push

    for i in range(len(g[now_node])) :
        # 현재 노드에 가중치를 더한것 : 현재 노드에서 연결된 노드로 넘어가는 비용이 더 적으면 update
        # 연결된 노드의 값을 update 할지 말지 결정해야 하기 때문에
        # dis[next_node]
        next_node = g[now_node][i][0]
        if g[now_node][i][1]+dis < distance[next_node] :
            distance[next_node] = g[now_node][i][1] + dis

            if not visited[next_node] :
                heapq.heappush(hq, (g[now_node][i][0], distance[next_node]))
                visited[next_node] = True

for i in range(1, V+1) :
    if distance[i] == INF :
        print('INF')
        continue
    print(distance[i])

'''
다익스트라 알고리즘

1. 시작 노드에서 각 노드들까지의 거리 확인
2. 그 중 최소 노드 확인
3. 최소 노드 방문
4. 해당 노드에서 다른 노드로 이동할 때 최소 거리 갱신
5. 노드 이동시 방문 처리

출력 : g[1] ~ g[V] 시작노드에서부터의 최단 거리
'''

 

틀린 이유

1. 힙에 넣을 때 현재는 (node, distance) 순서로 넣고 있는데, (dis, node) 순서로 넣어야 힙에서 pop 할 때, 최소 비용을 기준으로 나온다.

2. 가중치가 있기 때문에 g에 대해서 입력할 때 단방향 입력을 하였다. 따라서 visited를 검사할 필요 x

+ 다익스트라 알고리즘에서는 힙에서 꺼낼 때 방문 처리 해야 한다.

 

2차

import sys, heapq
input = sys.stdin.readline

V, E = map(int, input().split())
s_node = int(input())
INF = int(1e9) # 모든 간선의 가중치는 10이하의 자연수이다.

# 시작노드에서 각 노드에 대해 최소 거리를 저장할 리스트
distance = [INF for _ in range(V+1)] # 최단 거리를 구하는 거니까 다 큰 값으로 설정

# 노드는 1번부터 V까지 방문 여부 확인
# visited = [False for _ in range(V+1)]

g = [[] for _ in range(V+1)] # idx 노드에 대해 [연결노드, 가중치]
for _ in range(E) :
    u, v, w = map(int, input().split())
    # g[u] = [v,w] # 하나만 연결된게 아닐수도 있으니 append
    g[u].append([v,w])

hq = []
# heapq.heappush(hq, (s_node, 0)) # (거리, 노드) 순으로 넣어야 최소 거리 순으로 pop 된다!!
heapq.heappush(hq, (0, s_node)) # (거리, 노드) 순으로 넣어야 최소 거리 순으로 pop 된다!!
# visited[s_node] = True
distance[s_node] = 0 # 시작노드에서 시작 노드까지의 (최소)거리는 0

while hq :
    # 현재 노드, 거리
    dis, now_node = heapq.heappop(hq) # 최단거리를 알아서 먼저 pop

    # 현재 노드에 대해 연결된 노드들의 최단 거리 업데이트
    # g[now_node] 개수 -> 길이만큼 검사 : 연결된 노드에 대해서 최단거리 업데이트
    # 현재 노드와 연결된 노드들의 거리가 이전 보다 짧으면 update
    # 그 중 아직 방문하지 않은 노드는 heap_push

    for i in range(len(g[now_node])) :
        # 현재 노드에 가중치를 더한것 : 현재 노드에서 연결된 노드로 넘어가는 비용이 더 적으면 update
        # 연결된 노드의 값을 update 할지 말지 결정해야 하기 때문에
        # dis[next_node]
        next_node = g[now_node][i][0]
        if g[now_node][i][1]+dis < distance[next_node] :
            distance[next_node] = g[now_node][i][1] + dis

            # if not visited[next_node] :
                # heapq.heappush(hq, (g[now_node][i][0], distance[next_node]))
            heapq.heappush(hq, (distance[next_node], g[now_node][i][0]))
                # visited[next_node] = True

for i in range(1, V+1) :
    if distance[i] == INF :
        print('INF')
        continue
    print(distance[i])

'''
다익스트라 알고리즘

1. 시작 노드에서 각 노드들까지의 거리 확인
2. 그 중 최소 노드 확인
3. 최소 노드 방문
4. 해당 노드에서 다른 노드로 이동할 때 최소 거리 갱신
5. 노드 이동시 방문 처리
'''

 

주석 정리

import sys, heapq
input = sys.stdin.readline

V, E = map(int, input().split())
s_node = int(input())
INF = int(1e9)

distance = [INF for _ in range(V+1)]

g = [[] for _ in range(V+1)]
for _ in range(E) :
    u, v, w = map(int, input().split())
    g[u].append([v,w])

hq = []
heapq.heappush(hq, (0, s_node))
distance[s_node] = 0

while hq :
    dis, now_node = heapq.heappop(hq)
    
    for i in range(len(g[now_node])) :
        next_node = g[now_node][i][0]
        if g[now_node][i][1]+dis < distance[next_node] :
            distance[next_node] = g[now_node][i][1] + dis
            heapq.heappush(hq, (distance[next_node], g[now_node][i][0]))

for i in range(1, V+1) :
    if distance[i] == INF :
        print('INF')
        continue
    print(distance[i])