백준 1507 궁금한 민호

출처: www.acmicpc.net/problem/1507

분류: Greedy, Floyd Wharshall

---

접근방식

플로이드 와샬 알고리즘을 사용했습니다.

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최소 비용을 구하는 알고리즘입니다. 이 문제는 그 결과가 주어진 경우라고 할 수 있는데요,

주어진 간선 중에서 가중치가 가장 작은 것부터 연결해가면서 플로이드 와샬로 다시 가중치 그래프를 완성시켜 나갑니다.

연결하려고 하는 간선의 가중치가 만들고 있는 가중치 그래프와 같다면 이미 다른 경로를 통해 연결이 되어 있으므로 연결하지 않습니다.
작은 경우에만 새로 연결합니다.

불가능한 경우에는 -1을 출력하라고 했으니,

복귀를 다 마친 다음에 원본과 다르다면 -1을 출력해줍니다.

 

해결방법

let n = Int(readLine()!)!
var originGraph = [[Int]]()
var edges = [[Int]]()
var totalCost = 0

for from in 0..<n {
  let row = readLine()!.split(separator: " ").map {Int($0)!}
  originGraph.append(row)
  for (to, weight) in row.enumerated() {
    // from to weight
    if weight == 0 { continue }
    // 대각의 위쪽만 저장한다.
    if to > from {
      edges.append([from, to, weight])
    }
  }
}
// weight를 기준으로 오름차순 정렬
edges.sort(by: {$0[2] < $1[2]})

var graph = [[Int]](repeating: [Int](repeating: 10001, count: n), count: n)
for i in 0..<n {
  graph[i][i] = 0
}

func floydWarshall() {
  // 거쳐가는 노드
  for k in 0..<n {
    for from in 0..<n {
      for to in 0..<n {
        if from == to { continue }
        graph[from][to] = min(graph[from][k] + graph[k][to], graph[from][to])
      }
    }
  }
}

for edge in edges {
  // edge = [from, to, weight]
  let from = edge[0]
  let to = edge[1]
  let weight = edge[2]
  
  if weight < graph[from][to] {
    graph[from][to] = weight
    graph[to][from] = weight
    totalCost += weight
  }
  
  // 플로이드 와샬로 최소값 갱신
  floydWarshall()
}

graph == originGraph ? print(totalCost) : print(-1)

 

배운점

어제 혼자 해보다가 결국 못풀고.. 플로이드 와샬을 공부하고 쉽게 풀었다.

알고리즘 관련 영상을 보다가 이미 앞서 대단하신 "학자들이 오랜 시간 고민해서 만들어 놓은 알고리즘 이론들인데 이걸 내가 몇 시간만에 생각해낼 수 있겠냐, 못하는 것이 당연하다" 라는 말씀을 하시는 걸 봤는데, 정말 공감한다. 내가 그런 천재가 아닌 건 이미 뼈져리게 느끼고 있으니 이론, 방법을 열심히 익히고 공부하자. 베이스는 깔아두고 그 위에 쌓아야지.