지우너

문제https://www.codetree.ai/missions/8/problems/shortest-distance-9?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai   경로를 저장할 path[]배열 만들기path[i]에는 시작점으로부터 i번째 정점에 최단거리로 도달하기 위한 바로 직전 노드의 번호가 적히게 됩니다.도착지점부터 path배열 역추적(stack) 문제가 1-based인데, -1해서 저장하고 0-based로 풀고 마지막에 +1해서 출력하는 게 더 복잡한 거 같아서 그냥 1-ba..

그래프의 가중치가 없거나, 모든 간선의 가중치가 동일하다면 BFS를 이용하여 최단거리를 구할 수 있다.왜 쓰는가?그런데 가중치가 다를 경우, BFS를 이용하여 최단거리를 구하는 데에 어려움이 있다.이를 해결하기 위해 나온 알고리즘 중 하나가 다익스트라 알고리즘 언제 쓰는가?어떤 점에서 다른 모든점으로 가는 최단거리를 구할 때1~5까지의 점이 있고, 1에서 출발한다고 가정. 1-2의 최단거리, 1-3의 최단거리, 1-4의 최단거리, 1-5의 최단거리를 구할 수 있다는 의미 어떻게 쓰는가?기본 개념어떤 정점에서 시작해서 각 정점으로 가는 최단 거리를 구해야 한다. dist를 저장할 자료구조를 선택하고 시작 정점을 0, 나머지 정점을 inf로 초기화한다.(3번에서 시작한다고 가정했을 때, 3번으로 가는 최단거..