백준 1753 최단경로 파이썬 코딩테스트 문제 풀이 해답, 해설 및 설명 (난이도: G4, 기본)

백준 1753 최단경로 파이썬 코딩테스트 문제 풀이 해답, 해설 및 설명

문제 링크

1753번: 최단경로 (acmicpc.net)

문제 요약

주어진 방향 그래프의 시작점에서 다른 모든 정점을 방문할 수 있는 최단경로를 가중치를 고려하여 구한다.

코드 구현

언어: Python 3

결과

메모리: 68380 KB

시간: 544 ms

핵심 아이디어

1. 그래프의 표현: 입력으로 주어지는 각 정보를 바탕으로 인접 리스트를 사용해 그래프를 표현한다.
2. 다익스트라 알고리즘: 최단 경로를 찾기 위해 다익스트라 알고리즘을 활용한다.
3. 우선 순위 큐: 우선 순위 큐를 사용해 최단 경로 탐색을 수행한다.

추가 해설

주어진 입력 데이터가 많은 경우 sys.stdin.readline을 사용해 입력 데이터를 file object로 받아 각 줄을 반환하여 실행 시간을 줄인다.

• sys.stdin.readline()이란? 입력을 file object로 받아 첫 번째 줄을 반환한다. 그렇기에 입력을 받아 첫 번째 줄을 읽고 문자열로 변환한 후 줄 바꿈 문자를 제거하는 input()에 비해 많은 양의 입력을 빠르게 처리할 수 있다. (ref. Python)

인접 리스트로 표현한 그래프에서 시작 정점, 간선이 없는 경우 등을 알맞게 표현하고, 우선 순위 큐를 이용해 가중치를 비교하여 업데이트 한다.

혹시라도 문제 풀이와 코드 관련해서 궁금한 게 있다면, 댓글로 편하게 문의해주세요 🙂