난이도 : 골드 3유형 : 최단 경로 / 다익스트라링크 : https://www.acmicpc.net/problem/11779 구현 시간 : 30분    문제풀이해당 문제를 해결하기 위해서 다익스트라 알고리즘을 사용하여 출발 도시에서 각 노드(도시)까지의 최소 시간을 구하고, 동시에 이전 방문 노드를 저장해야 한다. 이를 위해 인접한 노드를 방문하며 최소 시간을 distance[] 배열에 갱신하고, 이와 함께 이전 노드를 preN[] 배열에 저장한다.이렇게 하면 특정 노드에 도달했을 때 해당 노드로 오기까지의 이전 노드를 추적할 수 있다.이후 최단 거리를 출력하고, Stack을 사용하여 방문 순서를 역순으로 출력한다. 핵심은 다익스트라 알고리즘에서 distance[] 배열을 갱신할 때, 이전 노드를 pr..

깊이 우선 탐색(DFS, Depth-First Search)DFS는 그래프 탐색 알고리즘 중 하나로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하여 차례대로 탐색하는 알고리즘이다. DFS는 주로 스택(Stack)을 통해 구현하거나, 재귀문을 통하여 구현한다.DFS 작동 원리1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다.3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.4. 2 ~ 3번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.   DFS의 작동원리를 이해하기 위해 아래 사진을 준비..