[백준] 1753 최단거리.py

pseeej·2021년 8월 16일

문제 링크 : https://acmicpc.net/problem/1753

💡 아이디어

문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

초기 접근

처음에 작성한 코드는 이렇다.

V, E = map(int, input().split())
K = int(input())

# 충분히 큰 수로 배열 초기화
arr = [[int(1e9) for i in range(V+1)] for i in range(V+1)]

for i in range(E):
    a, b, c = map(int, input().split())
	  arr[a][b] = c # 주어진 위치에 dist 값 넣어줌

# 자기 자신의 거리는 0으로 설정
for i in range(V+1):
    arr[i][i] = 0

for i in range(1, V+1):
    key = arr[K][i]
    if key==0: # 자기 자신을 가리키는 경우 그냥 끝냄
        print(key)
        continue
    
    for j in range(1, V+1): # 거쳐가는 길 확인
        if arr[j][i] < key: # 거쳐가는 길을 기준으로 원래보다 크면 걍 지나침
            temp = arr[K][j] + arr[j][i] # 거리 새로 초기화
            key = min(temp, key)
    
    print(key)

2차원 배열에 start, end, distance 내용을 기록
시작하는 vertex의 행을 기준으로 하나씩 검사
1. 자기 자신을 가리키는 경우, 그냥 출력하고 끝냄
2. 본인을 거치는 길을 기준으로 새로 탐색.
  
  (1-3-2 식으로 지나가려고 생각한다면, 3을 기준으로 탐색(열 탐색).
  
  3으로 들어오는 애들이 누가 있는지)
3. 만약 새로 탐색한 길이 이전에 찾아놨던 길보다 더 별로면 걍 지나침
4. 새로 탐색한 길로 새로운 거리 계산
5. 이전의 거리와 새로운 거리 비교하여 더 작은 값을 최종 값으로 넣기

근데 이렇게 했더니 메모리 초과가 떴다... 질문 검색하기 들어가보니 저게 2차원 배열이라 2만 개가 들어오면 엄청 커질 거다,,,~ 하더라궁

[백준/Python] 1753 - 최단경로

최종 접근

그래서,,, Dijkstra 알고리즘을 열심히 설명해둔 나동빈씨의 블로그를 다시 봤다.

23. 다익스트라(Dijkstra) 알고리즘

이 나동빈씨가 구현한 C++코드를 그대~로 python으로 옮겼다고 해도 무방하다... 알고리즘은 정말 Dijkstra의 정석. 그대로였음.
Python에서 우선순위 큐는 또 처음 써봐서... 검색해서 써봤다

파이썬의 우선순위 큐(PriorityQueue) 사용법

또 이렇게 내가 tuple 형식으로 넣었다면... 정렬할 때 제일 앞 값을 기준으로 우선순위 큐를 만들어낸다고 하더라. 그래서 중간에... 내가 처음에 heappush(pq, (K, 0)) 형태로 넣었던 걸 heappush(pq, (0, K)) 로 바꿔서 넣었다. 나는 거리 기준으로 정렬을 할 거니깐!
내가 이렇게까지 했는데,,, 계속해서 시간초과가 떴다... 그래서 혹시나! 이 priority queue가 잘못된건가? 싶어서 질문 검색하고,,, 아래 사람처럼 heapq로 바꿔서 풀어봤다. 그냥 형식만 priority queue에서 heapq로 바꿨을 뿐, 다른 건 바꾸지 않았다.

글 읽기 - 1753 파이썬 구현 시간초과

근데 그래도 시간초과!!!!!!!!!1가 나더라................. 그래서,,, 하다가 짜증나서 덮어놨다가,,, 애들이랑 줌 할 때 내 코드를 하나씩 뜯어봤다 ~~(아마도)~~
그랬더니 맹진이가... heappush(pq, (-next_dist, next_vert)) 여기에서 굳이 -가 필요할까?? 라고 했다... ~~난 그냥 나동빈씨가 하라는 대로 했는데...~~ 그래서 -를 빼고 다시 했더니 되더라................. 내 정답률 어떡할거야...........................
그래서 생각해보니 내가 참고했던 저 질문 게시판에 올린 사람도 heapq를 썼는데 -를 안 썼더라... 이건... Python과 Cpp의 차이인 것 같다.

Python에서의 heapq는 최소 힙이고, cpp에서의 priority queue는 최대 힙

처음에 python에서는 오름차순, cpp에서는 내림차순이다! 하고 적어놨더니 맹진이가 고쳐줬따.
뭐 아무튼 그래서 python에서는 - 처리할 필요가 전혀 없었던 거였다.......... 핫...핫...핫........

[파이썬] heapq 모듈 사용법

📋 사용 스펙

어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

최소 heap
graph
Dijkstra

👨🏻‍💻 👩‍💻 코드

from heapq import heappush, heappop
# 시간 줄이기 위해서...
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())

arr = [[] for i in range(V+1)]  # 입력받은 내용 저장할 배열

for i in range(E):
    a, b, c = map(int, input().split())
    arr[a].append((b, c))   # 인접 리스트 형식? a 자리에 (end vertex, distance) 형태로 저장
    
res = [int(1e9) for i in range(V+1)]    # 큰 값으로 최종 계산한 거리 배열 초기화
pq = []
heappush(pq, (0, K))    # python에서의 최소힙에 (distance, vertex) 형태로 저장

res[K] = 0  # 나!는 최단거리가 0이지~
while pq:
    dist, vertex = heappop(pq)  # 힙에서 하나씩 빼오기

    if res[vertex] < dist:  # 만약 저장된 거리가 충분히 작으면 걍 넘김
        continue

    for next_vert, d in arr[vertex]:    # 그 다음의 vertex와 거리 받아오기
        next_dist = d + res[vertex] # 새로운 거리 계산. 이전에 저장된 내용에 새로운 거리 더해서 새로운 루트? 만들어냄

        if next_dist < res[next_vert]:  # 새로 만든 방법? 루트가 더 짧으면
            res[next_vert] = next_dist  # update 시켜주고
            heappush(pq, (next_dist, next_vert))    # heap에 넣어줌

# 출력
for i in range(1, V+1):
    if res[i] == int(1e9):
        print("INF")
    else:
        print(res[i])