1. 문제 설명

다리 만들기 2

2. 문제 분석

BFS를 사용한 컴포넌트 분리 + BFS를 이용한 노드 별 최단 거리를 통한 간선 만들기 + 크루스칼 알고리즘을 통한 MST의 청 세 가지 기법을 결합해 푸는 문제.

• 파이썬으로 이전에 풀었던 문제로, 크루스칼 알고리즘에 넣어줄 데이터 전처리 과정이 관건인 문제다. 크루스칼 알고리즘은 간선 비용을 통해 MST를 구하는 문제이기 때문이다.

1. 이 경우 인접 행렬을 구성하는 각 컴포넌트에 번호를 주고 분리한다. (BFS 등 사용)
2. 각 컴포넌트 별 최단 경로(수직/수평만 가능) 및 최소 거리(1 초과) 등 조건에 따라 간선을 얻는다. (BFS 등 사용)

생각해보니 BFS 이외에도 x축, y축 중 하나가 같은 좌표 간의 거리가 곧 간선 비용이기 때문에 각 컴포넌트 별 좌푯값을 조회해서 구할 수 있을 것 같다.

3. 얻은 간선을 통해 곧바로 크루스칼 알고리즘을 사용한다.

3. 나의 풀이

import Foundation

let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var nodes = [[Int]]()
for _ in 0..<N{
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    nodes.append(line)
}
var islands = [[(Int, Int)]]()
var num = 2
for i in 0..<N{
    for j in 0..<M{
        if nodes[i][j] == 1{
            let island = BFS(curRow:i, curCol:j, num:num)
            islands.append(island)
            num += 1
        }
    }
}

var pq = [(Int, Int, Int)]()
var edgeCheck = Array(repeating: Array(repeating: false, count: islands.count+2), count: islands.count+2)
var nodeNum = 2
for island in islands{
    makeEdge(startNodes:island, nodeNum:nodeNum)
    nodeNum += 1
}
pq.sort(by: {$0.0 < $1.0})
var parents:[Int] = []
for i in 0..<(islands.count + 2){
    parents.append(i)
}
let answer = Kruskal()
print(answer)

func BFS(curRow:Int, curCol:Int, num:Int)-> [(Int, Int)]{
    var queue = [(Int, Int)]()
    queue.append((curRow, curCol))
    nodes[curRow][curCol] = num
    var index = 0
    while queue.count > index{
        let curRow = queue[index].0
        let curCol = queue[index].1
        
        for i in 0..<4{
            let nextRow = curRow + dy[i]
            let nextCol = curCol + dx[i]
            if nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M{
                continue
            }
            if nodes[nextRow][nextCol] == 1{
                nodes[nextRow][nextCol] = num
                queue.append((nextRow, nextCol))
            }
        }
        index += 1
    }
    return queue
}

func makeEdge(startNodes:[(Int, Int)], nodeNum:Int)->Void{
    var queue = [(Int, Int, Int, Int)]()
    for startNode in startNodes{
        queue.append((startNode.0, startNode.1, 0, 0))
        queue.append((startNode.0, startNode.1, 1, 0))
        queue.append((startNode.0, startNode.1, 2, 0))
        queue.append((startNode.0, startNode.1, 3, 0))
    }
    let node1 = nodeNum
    edgeCheck[node1][node1] = true
    while queue.isEmpty == false{
        let curData = queue.removeFirst()
        let curRow = curData.0
        let curCol = curData.1
        let curDir = curData.2
        let curCost = curData.3
        let nextRow = curRow + dy[curDir]
        let nextCol = curCol + dx[curDir]
        if nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M{
            continue
        }
            
        if nodes[nextRow][nextCol] == 0{
            queue.append((nextRow, nextCol, curDir, curCost+1))
        } else if nodes[nextRow][nextCol] != node1 && nodes[nextRow][nextCol] > 1 && edgeCheck[node1][nodes[nextRow][nextCol]] == false && curCost > 1{
            let node2 = nodes[nextRow][nextCol]
            edgeCheck[node1][node2] = true
            edgeCheck[node2][node1] = true
            pq.append((curCost, node1, node2))
        }
    }
}


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

func union(node1: Int, node2: Int) -> Bool{
    let root1 = find(node:node1)
    let root2 = find(node:node2)
    if root1 == root2{
        return false
    } else {
        parents[root2] = root1
        return true
    }
}

func Kruskal() -> Int{
    var total = 0
    var edgeCnt = 0
    for curData in pq{
        let curCost = curData.0
        let node1 = curData.1
        let node2 = curData.2
        if union(node1: node1, node2: node2){
            total += curCost
            edgeCnt += 1
            if edgeCnt == islands.count-1{
                return total
            }
        }
    }
    return -1
}