결국 빛나리라

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에서 갈 수 있는 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net > 플로이드 워셜 전형적인 플로이드 워셜 알고리즘 유형의 문제이다. https://westshine-data-analysis.tistory.com/45?category=843975 최단경로 알고리즘(3)/ 플로이드 워셜 알고리즘 나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-fo..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 플로이드 워셜 알고리즘이란? 모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘으로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 2차원 테이블에 최단거리 정보를 저장하고 점화식에 따라 거리 정보를 갱신하는 원리로 다이나믹 프로그래밍 유형에 속한다. 점화식은 각 단계 즉 k의 노드를 점검할 때마다 a에서 b로 가는 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧을 때 해당 값으로 거리정보를 갱신하는 원리를 사용한다. 따라서 점화식은 다음과 같다. Dab= min(Dab, Dak+ Dk..