백준 1753

<최단 경로 구하기>

난이도 : 골드 5

1. 백준 문제
   1753

2. 코드 알고리즘

• 다익스트라 개념
  

선택노드가 될 때마다 다시 선택되지 않도록 한다. 다시 선택되어도 가중치가 양수니까 계속 증가하므로 최단거리가 될 수 없다.
각 단계마다 탐색노드로 한번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 작은 값으로 다시 갱신되지 않는다 ❗

• 1753

2-1. 슈도 코드

v, e 입력
시작 정점
u, v, w 입력 됨 -> e개 만큼

인접리스트 구현하기
(v, w) 형태로 append

distance를 [0, max, max...]로 설정

우선순위 큐
최초 시작점 큐 삽입
while q.size()>0:
	큐에서 거리 리스트 값이 가장 작은 노드 선택 #★이걸 생각 못했어!!
	#왜?? -> 그래야 다음 노드가 최단 거리로 업데이트 되니까(각각 한번 방문하더라도)
	해당 노드의 인접리스트 가져오기
	[자식 노드 거리 리스트] > [출발 노드 거리 리스트] + [에지 가중치] -> 업데이트
	업데이트된 노드를 우선순위 큐에 삽입

완성된 거리 리스트 출력
max일 경우 INF 출력
	

3. 코드

from queue import PriorityQueue

n, e = map(int, input().split())
k = int(input())

#인접리스트 작성
A =[[] for _ in range(n+1)]
for i in range(e):
    u, v, w = map(int, input().split())
    A[u].append((v, w))

#distance 초기화
max = sys.maxsize
D = [max]*(n+1)
D[k] = 0

#방문 리스트
visited = [False]*(n+1)

#우선 순위 큐
q = PriorityQueue()
q.put((0, k)) #거리로 정렬되도록 먼저 작성하기
while q.qsize()>0:
    now = q.get() #거리리스트 값이 가장 작은 노트 선택(이미 우선정렬된 큐)
    now_s = now[1] #출발 노드
    if not visited[now_s]: #방문 안한 경우에만
        visited[now_s] = True
        for v,w in A[now_s]: #v는 도착 노드
            #출발노드의 방문 유무를 확인해야하는지, 도착노드 방문 유무를 확인해야하는지 헷갈림
            if D[v] > D[now_s] + w and not visited[v]:
                #여기서 먼저 방문체크 다해버리면 안되는건가...? (우선순위가 영향주나?)
                #예를 들어 2, 3, 4 한꺼번에 다 큐에 들어가고 방문체크 됐는데
                # 2가 4를 탐색할 수 없게 되버린
                #근데 노드가 처음으로 선택된 때에 최단거리가 결정되는 거잖아
                D[v] = D[now_s] + w
                q.put((D[v], v)) #거리값이 우선 오도록

#최종 결과 출력
for i in range(1, n+1):
    if D[i] == max:
        print("INF")
    else:
        print(D[i])

4. 코드 후기

   항상 자신이 부족하다는 것을 염두에 두자

다익스트라를 계속 틀린 이유는 제대로 개념을 100% 이해하지 않은 상태에서 시도했기 때문이다. 그러면서 자신의 코드가 틀릴 의심도 하지 않았다...

특히 코테는 사전준비를 100%로 하고 시도하자

개념을 제대로 공부했는지(다른 velog 글도 참조하면서 나만의 언어로 정리하기)/ 슈도코드도 꼼꼼히 작성하기/ 게시판의 테케도 확인하며 반례 보완해나가기

• 방문을 1번만 한다
  그래서 최단거리를 이용해 우선정렬을 해야된다.

예를 들어 1 노드 다음 2와 3이 선택됐는데 
3의 거리리스트가 더 작은 경우 3을 선택해야된다. 
2와 3과 연결된 노드 4의 최단거리는 3의 최단거리 + 가중치이기 때문이다.

우선 정렬 큐에서 (거리리스트, 노드) 로 삽입을 해서 거리리스트가 작은 노드가 우선순위로 오도록 한다.

• 계속 2%에서 틀린 이유
  인접리스트에서 도착노드들을 큐에 삽입할 때 한꺼번에 방문체크 했는데 (아래 코드)

for v, w in A[node_s] and not visited[v]:
	visited[v] = True

while문 초기에 방문체크해야 됐다.

while q.size()>0:
	now = q.get()
    now_s = now[1]
    if not visited[now_s]:
    	#다익스트라 실행...

아직 왜 이래야 되는지에 대한 반례는 못찾았다.
즉, while문 초기에 방문체크를 검사하고 방문하지 않았으면 방문체크를 한 후 다익스트라 실행