# Shortest Path
백준 #11779 최소비용 구하기 2 (파이썬)
아주 전형적인 다익스트라 문제다. 하지만 최단 비용만 출력하는 게 아니라 그때의 경로를 함께 출력해야 하므로 추가 변수가 필요하다.
다익스트라, 벨만-포드, 플로이드-워셜 함수 핵심부만 모아보기
위 글이 너무 길어서 구현 부분을 따로 보면서 외우기가 힘드니까 구현부만 발췌한 글을 새로 작성한다. 알고리즘에 대한 설명은 따로 하지 않겠다.
최단 경로 알고리즘 : 다익스트라 VS 벨만-포드 VS 플로이드-워셜
솔브닥 CLASS 4의 난관이자 코딩테스트를 위해 반드시 넘어야 하는 벽인 최단 경로 알고리즘에 대해 소개한다. 눈으로 보지만 말고, 반드시 직접 파이썬으로 구현해보자!
[Python] 백준 11265 - 끝나지 않는 파티 문제 풀이
분류: Shortest Path (최단거리), Dijkstra(다익스트라), Floyd-Warshall(플로이드와샬)
백준 1956, 운동 - 플로이드-와샬
https://www.acmicpc.net/problem/1956각 도시(노드)에서 출발하여, 해당 도시(노드)로 돌아오는 싸이클의 최소 가중치 합모든 노드 -> 나머지 다른 모든 노드의 최단경로=> 플로이드-와샬 (dist\[i]\[i] = 0 초기화)모든
백준 11403, 경로 찾기 - 플로이드-와샬
https://www.acmicpc.net/problem/11403모든 정점 -> 다른 모든 정점으로 탐색=> 플로이드-와샬예외처리) 노드 본인에서 출발하여 다시 되돌아오는 싸이클 구성하는지 확인 필요비용 배열 초기화 시, 노드 본인 -> 본인의 비용dist\
백준 1389, 케빈 베이컨의 6단계 법칙 - 플로이드-와샬
https://www.acmicpc.net/problem/1389케빈 베이컨의 수 = "모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합"모든 노드 -> 나머지 모든 노드=> 플로이드-와샬\[i]번 노드의 케빈 베이컨 수 = \[i]행 dist\[i
백준 2660, 회장 뽑기 - 플로이드-와샬
https://www.acmicpc.net/problem/2660\[i]번 회원의 점수 = 가장 먼 회원과의 거리 (최대 거리)모든 회원(노드) -> 다른 모든 회원(노드)의 거리=> 플로이드-와샬1) 비용 배열 초기화dist\[]\[] 모든 원소 INF로 초
백준 11404, 플로이드 - 플로이드-와샬
https://www.acmicpc.net/problem/11404플로이드-와샬모든 노드 -> 다른 모든 노드로 갈 때, 최소 비용음의 가중치 가능1) 비용 배열 초기화cost\[i]\[i] = 0, 나머지 cost\[i]\[j] = INFINF = (노드 최
백준 13549, 숨바꼭질 3 - 다익스트라 / BFS
https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로
백준 2665, 미로 만들기 - 다익스트라
https://www.acmicpc.net/problem/2665단순히 시작 지점 \[0]\[0] -> 끝 지점 \[n-1]\[n-1]으로의 최단경로는 BFS로 해결 가능.하지만, 방을 바꾸는 최소 개수에 해당하는 경로는 최단경로가 아닐 수 있음시작 지점으로부
백준 1504, 특정한 최단경로 - 다익스트라
https://www.acmicpc.net/problem/1504case 1) 1번 노드 -> v1 노드 -> v2 노드 -> n번 노드1번 노드 -> v1 노드 최단경로 다익스트라v1 노드 -> v2 노드 최단경로 다익스트라v2 노드 -> n번 노드 최단경로
백준 1753, 최단경로 - 다익스트라
https://www.acmicpc.net/problem/1753다익스트라한 노드 -> 다른 모든 노드로의 최단거리음이 아닌 간선의 가중치1) 비용 배열, 우선순위 큐 초기화dist\[]: 시작 노드 거리 0, 나머지 노드 무한대pq: (시작 노드, 0) 추가
