목록역추적 (1)

Doby's Lab

[알고리즘] 백준 1719번: 택배 (C++), 경로 역추적

https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 이번 문제에서 해결해야 하는 건 "최단 경로를 구했을 때 시작 노드에서 제일 처음 방문한 노드가 어디인가"를 어떻게 찾을지가 포인트였다. (참고 https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-1719-%ED%83%9D%EB%B0%B0) 참고한 포스팅에서 다음과 같이 정리할 수 있었다. 1) 다익스트라를 통해 각 노드로부터 최단 경로 구하기 2) 최단 거..
PS/BOJ 2021. 12. 5. 16:28
이전 Prev 1 Next 다음