결국 빛나리라

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net > 문제 풀이 아이디어 bfs와 최단거리 유형으로 풀 수 있다. - 시작점인 1을 큐(q)에 넣고 최단 거리정보를 나타낸 dist 리스트의 시작점엔 0을 넣는다. - 1에서 갈 수 있는 노드는 2와 3이므로 이들을 q에 차례로 넣는다. 동시에 최단거리는 (0+1)로 dist의 각 인덱스에 추가해준다. - 2에서 갈 수 있는 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ DFS (Depth-First Search) 란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 시작노드에서 시작하여 인접한 노드들을 방문하며 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색한다. 인접한 리스트가 여러개일 경우 노드의 숫자가 가장 낮은 방향으로 탐색한다. > 다음 그래프가 있을 때 DFS는 어떤식으로 탐색할까? (설명 뒤의 []는 쌓이는 스택을 표현한 것이다) - 1에서 탐색을 시작한다. [1] - 연결된 노드 2,8,6중 가장 낮은 수인 2로 탐색한다. [1,2] - 2에서 3으로 방문한다. [1..