백준 #1238 - 파티
벨만포드 : 한 점에서 다른 점들로 이동하는 최단 거리 계산
다익스트라 : 한 점에서 다른 점들로 이동하는 최단 거리 계산
한번도 도달하지 못한 점이거나, 해당 점에서의 최단거리가 갱신되면 거기서 dfs를 돌리는 방식으로도 해결 가능. 일종의 벨만포드에 속할듯?
벨만포드 : 모든 간선에 대해 더 짧게 갱신할 수 있는 거리를 모두 갱신해준다. n-1번 (최단 경로 중 가장 많이 간선을 선택하는 경우가 n-1개) 반복.
효율 개선법 1. 더이상 갱신되는게 없으면 종료
효율 개선법 2. SPFA(Shortest Path Faster Algorithm) 거리를 줄이는데 사용될 수 있는 노드를 별도의 큐로 관리하고 그 노드만 처리한다.
특징 : 음수 간선을 포함한 사이클이 있다면 사용 불가. 그런 사이클이 있는지 판별도 가능하다.
다익스트라 : 모든 간선들을 한번씩만 탐색하기 때문에 벨만포드보다 효율적이다.
특징 : 음수 간선이 없다는 전제 하에 타겟 노드들을 한번씩만 체크하게된다.
아직 처리하지 않은 노드들 중 거리가 가장 가까운 노드를 다음 타겟으로 잡는다. 타겟 노드부터 이웃한 노드들까지의 거리를 갱신. 끝! 이걸 모든 노드에 대해 반복한다.
파티 문제의 경우 각 마을에서 파티 지점으로, 파티 지점에서 각 마을로 돌아가야한다.
파티 -> 각 마을 은 파티~ 각 마을 최단경로탐색 한 번으로 모두 구할 수 있음.
그렇다면 각 마을->파티 는? 다익스트라를 n번 돌려야할까?
모든 간선을 역으로 뒤집은 그래프를 하나 만들고, 파티지점에서 시작하는 다익스트라를 구해는 방식으로 해결할 수 있다. 놀랍게도!
플로이드와샬 : 모든 정점에서, 모든 정점으로의 최단 거리 계산
2차원 배열에 저장하며 연산
'Algorithem' 카테고리의 다른 글
| 수학 : 최대공약수와 최소공배수, 소수 구하기 (0) | 2023.01.06 |
|---|---|
| 최장 공통 부분 수열 (LCS) : 다이나믹, 2차원배열, 역추적 (0) | 2023.01.06 |
| 수행 시간 추정 : 시간복잡도, 입력의 크기 (0) | 2023.01.06 |
| 엄청 큰 거듭제곱 : 지수 분할 (0) | 2023.01.05 |
| 최장 증가 부분 수열 (LIS) : 수열 길이마다 최대값 갱신 (0) | 2023.01.05 |
