백준 1753번1 [백준 1753번] 최단경로 (Python 풀이) https://www.acmicpc.net/problem/1753 문제 문제 이해 먼저, 문제의 제목처럼 최단경로를 구하는 문제이다. 선뜻, BFS (너비우선탐색)이 생각나지만, 이 문제는 가중치가 있다. 1, 0 으로 이루어진 가중치라면 BFS풀이가 가능하나, 1을 초과하는 가중치가 있기 때문에 이 문제는 BFS로 풀지 못한다. 즉, Dijkstra (다익스트라) 알고리즘을 사용한다. 첫째 줄에는 노드 수, 간선 수가 나온다. 여기서 간선이라고 하는 것은 가중치가 있고 방향이 있는 화살표이다. (양쪽을 향하는 화살표가 아니란 말이다.) 예제 입력을 그림으로 나타내면 저런 형태를 가진다. 풀이 방법 1. 먼저 간선(v)과 가중치(e)가 들어가는 edge 배열을 만든다.위의 예제 입력의 edge 배열은ed.. 2023. 5. 4. 이전 1 다음
