플로이드 와샬
-
백준 11404 플로이드Algorithm/BOJ 2021. 4. 7. 11:59
출처: www.acmicpc.net/problem/11404 분류: 플로이드 와샬 접근방식 이름처럼 전형적인 플로이드 와샬 문제였습니다. 플로이드 와샬 알고리즘을 알면 쉽게 풀 수 있었던 문제였네요! 플로이드 와샬이 익숙하지 않으시다면 여기로 :] 해결방법 let n = Int(readLine()!)! var values = [[Int?]](repeating: [Int?](repeating: nil, count: n+1), count: n+1) for i in 1...n { values[i][i] = 0 } for _ in 0..
-
백준 1507 궁금한 민호Algorithm/BOJ 2020. 6. 18. 13:33
출처: www.acmicpc.net/problem/1507 분류: Greedy, Floyd Wharshall 접근방식 플로이드 와샬 알고리즘을 사용했습니다. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최소 비용을 구하는 알고리즘입니다. 이 문제는 그 결과가 주어진 경우라고 할 수 있는데요, 주어진 간선 중에서 가중치가 가장 작은 것부터 연결해가면서 플로이드 와샬로 다시 가중치 그래프를 완성시켜 나갑니다. 연결하려고 하는 간선의 가중치가 만들고 있는 가중치 그래프와 같다면 이미 다른 경로를 통해 연결이 되어 있으므로 연결하지 않습니다. 작은 경우에만 새로 연결합니다. 불가능한 경우에는 -1을 출력하라고 했으니, 복귀를 다 마친 다음에 원본과 다르다면 -1을 출력해줍니다. 해결방법 let n =..
-
Floyd Wharshall 플로이드 와샬Algorithm/Theory 2020. 6. 18. 13:24
목표 - 하나의 정점에서가 아닌 모든 정점에서 모든 정점으로 가는 최단 경로를 구하고 싶을 때 사용한다. - 거쳐가는 정점을 기준으로 알고리즘을 수행한다. - 삼중 for문을 사용해 구현하므로 O(n^3)의 시간 복잡도를 갖는다. 플로이드 와샬 알고리즘 ? 플로이드 와샬 알고리즘은 한 정점에서 시작해 모든 정점을 탐색하는 최단 방법을 다룬 다익스트라나 다른 그래프 탐색 알고리즘과 달리 모든 정점에서 모든 정점의 최단 경로를 구하고 싶을 때 사용합니다. 핵심 아이디어는 A -> B 노드로 갈 때, A -> B 로 바로 가는 경우 와 A -> K -> B 로 어떤 노드 k를 거쳐가는 방법 을 비교해서 최소값을 구하자는 것입니다. 구현은 가중치 테이블을 이용합니다. 아직 연결이 되지 않은 노드는 ∞으로 두고 ..