백준 - 다리 만들기 2 (17472)

struct Edge {
    let start: Int
    let end: Int
    let value: Int
}

// 위, 오, 아래, 왼
let row = [-1, 0, 1, 0]
let col = [0, 1, 0, -1]

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M) = (input[0], input[1])
var map = [[Int]]()
var islands = [[[Int]]]()

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    map.append(input)
}

// DFS 실행해서 각 섬 구분
var visited = Array(repeating: Array(repeating: false, count: M), count: N)
var nowIsland = [[Int]]()
var islandCount = 1

for i in 0..<N {
    for j in 0..<M {
        if map[i][j] != 0 && !visited[i][j] { // 방문하지 않은 섬 발견
            nowIsland = [[Int]]()
            dfs(i, j)
            islandCount += 1
            islands.append(nowIsland)
        }
    }
}

func dfs(_ x: Int, _ y: Int) {
    if visited[x][y] || map[x][y] == 0 { return }
    visited[x][y] = true
    map[x][y] = islandCount
    nowIsland.append([x, y])
    for i in 0..<4 {
        let nextX = x + row[i]
        let nextY = y + col[i]
        if nextX >= 0 && nextX < N && nextY >= 0 && nextY < M {
            dfs(nextX, nextY)
        }
    }
}

// 모든 가능한 다리 만들기
var queue = Heap<Edge>(sort: { $0.value < $1.value })

for island in islands {
    for now in island {
        let x = now[0]
        let y = now[1]
        let nowNumber = map[x][y]
        for i in 0..<4 { // 네 방향 검색하기
            var length = 0
            var tempX = x + row[i]
            var tempY = y + col[i]
            while tempX >= 0 && tempX < N && tempY >= 0 && tempY < M {
                if map[tempX][tempY] == nowNumber { // 같은 섬이면
                    break
                } else if map[tempX][tempY] != 0 { // 다른 섬이면
                    if length > 1 {
                        queue.insert(Edge(start: nowNumber, end: map[tempX][tempY], value: length))
                    }
                    break
                } else {
                    length += 1
                }
                if row[i] == -1 { tempX -= 1 } // 위로
                else if row[i] == 1 { tempX += 1 } // 아래로
                else if col[i] == -1 { tempY -= 1 } // 왼쪽으로
                else if col[i] == 1 { tempY += 1 } // 오른쪽으로
            }
        }
    }
}

// 최소 신장 트리 알고리즘 수행
var parent = Array(0..<islandCount)
var useEdge = 0
var result = 0

while !queue.isEmpty() {
    let now = queue.remove()!
    if find(now.start) != find(now.end) { // 같은 부모 아님 -> 연결 가능
        union(now.start, now.end)
        useEdge += 1
        result += now.value
    }
}

if useEdge == islandCount - 2 {
    print(result)
} else {
    print("-1")
}

func find(_ node: Int) -> Int {
    if parent[node] == node {
        return node
    }
    parent[node] = find(parent[node])
    return parent[node]
}

func union(_ a: Int, _ b: Int) {
    let aParent = find(a)
    let bParent = find(b)
    if aParent < bParent {
        parent[bParent] = aParent
    } else {
        parent[aParent] = bParent
    }
}

이 문제를 푸는 과정은 크게 3가지로 나뉜다.

1. 각 섬들 구분하기
   • 지도 전체를 순회하면서 방문하지 않은 섬을 발견하면 DFS 또는 BFS를 사용해서 현재 섬과 같은 표시를 한다.
   • 이때 각 섬마다 섬을 이루고 있는 좌표 값들을 모두 저장한다.
2. 각 섬마다 다른 섬으로 연결되는 다리가 있는지 확인하고 에지 리스트 만들기
   • 1에서 저장한 섬들의 좌표 정보를 가지고 상하좌우로 탐색하며 다른 섬에 도착할 수 있는지 확인한다.
   • 계속 탐색하다가 다른 섬을 만나고 다리 길이가 1보다 크면 에지 리스트에 추가(== 다리를 지을 수 있음)하고, 바다를 만나면 다리 길이를 1 더하고 계속 반복한다. 그리고 같은 섬을 만났을 때는 바로 탐색을 종료한다.
3. 2번에서 구한 에지 리스트를 사용해서 최소 신장 트리 만들기
   • 모든 섬이 다 연결되지 않는 경우가 있기 때문에 우선순위 큐의 값이 존재하는 동안 반복문을 돌린다.

3까지 수행한 다음 사용된 에지의 개수가 섬의 개수 - 1 보다 작으면 모든 섬을 연결할 수 없는 것으로 간주하고 -1 을 출력한다.

아이디어를 떠올리고 구현하는 게 어려웠던 문제였다..