[백준] 17472번: 다리 만들기 2 - Kotlin[코틀린]

문제

 

17472번: 다리 만들기 2

 

---

풀이

 

 이 문제의 풀이 과정과 사용한 알고리즘은 다음과 같다.

 

 1. 섬에 고유 번호 부여 (DFS): 입력받은 지도를 DFS나 BFS를 이용하여 각 섬에 번호를 부여해준다. 입력에서 1이 섬이기 때문에 첫번째 섬부터 2번으로 부여해주었다.

 

 2. 각 섬을 연결할 수 있는 방법 구하기 (BFS): 각 섬을 연결하는 가능한 모든 다리를 찾아준다. 길이가 1보다 큰 다리들을 거리에 따라 오름차순으로 정렬될 수 있게 우선 순위 큐에 저장한다.

 

 3. 최소 신장 트리(MST) 구하기 (크루스칼): 우선 순위 큐에 저장된 다리 정보를 활용하여 크루스칼 알고리즘을 수행한다. MST를 구하고 이를 통해 최소 비용을 계산한다.

 

 최종적으로 구한 MST가 올바르게 형성되었다면 최소 비용을 출력하고, 그렇지 않다면 -1을 출력한다.

 

---

코드

 

import java.util.*

data class Point(val x: Int, val y : Int, val value: Int)
data class Edge(val start: Int, val end: Int, val value: Int) : Comparable<Edge> {
    override fun compareTo(other: Edge): Int = value.compareTo(other.value)
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val rows = st.nextToken().toInt()
    val cols = st.nextToken().toInt()

    val map = Array(rows){ IntArray(cols) }
    repeat(rows) { i ->
        StringTokenizer(br.readLine()).run {
            repeat(cols) { j ->
                map[i][j] = nextToken().toInt()
            }
        }
    }

    // 탐색 가능 범위
    val dx = arrayOf(-1, 0, 1, 0)
    val dy = arrayOf(0, 1, 0, -1)
    fun isRange(nx: Int, ny: Int) = nx in 0 until rows && ny in 0 until cols

    // 섬 번호 붙이기
    fun dfs(x: Int, y: Int, idx: Int) {
        map[x][y] = idx
        for(i in 0 until 4) {
            val nx = x + dx[i]
            val ny = y + dy[i]
            if (isRange(nx, ny) && map[nx][ny] == 1) {
                dfs(nx, ny, idx)
            }
        }
    }

    var island = 2
    repeat(rows) { i ->
        repeat(cols) { j ->
            if (map[i][j] == 1) {
                dfs(i, j, island++)
            }
        }
    }

	// 다리 정보 저장을 위한 우선순위 큐
    val pq = PriorityQueue<Edge>()

    // 경로 만들기
    fun makeBridge(x: Int, y: Int, idx: Int) {
        for(i in 0 until 4) {
            val queue : Queue<Point> = LinkedList()
            queue.add(Point(x, y, 0))

            while(queue.isNotEmpty()) {
                val tmp = queue.poll()
                val nx = tmp.x + dx[i]
                val ny = tmp.y + dy[i]

                if(isRange(nx, ny)) {
                    if(map[nx][ny] == idx) continue
                    if(map[nx][ny]==0) {
                        queue.add(Point(nx, ny, tmp.value + 1))
                    } else {
                        if(tmp.value > 1) {
                            pq.add(Edge(idx, map[nx][ny], tmp.value))
                        }
                    }
                }
            }
        }
    }

	// 모든 섬에 대해 다리 정보 생성
    repeat(rows) { i ->
        repeat(cols) { j ->
            if (map[i][j] != 0) {
                makeBridge(i, j, map[i][j])
            }
        }
    }

	// 크루스칼 알고리즘을 위한 유니온-파인드
    val parent = IntArray(island){ it }
    fun find(a: Int) : Int {
        if (parent[a] != a) {
            parent[a] = find(parent[a])
        }
        return parent[a]
    }
    fun union(a: Int, b: Int) {
        val x = find(a)
        val y = find(b)
        if(x<y) {
            parent[y] = x
        } else {
            parent[x] = y
        }
    }
    
    // 크루스칼 알고리즘으로 MST 구하기
    fun kruskal(): Int {
        var sum = 0

        while(pq.isNotEmpty()) {
            val edge = pq.poll()
            if(find(edge.start)!=find(edge.end)) {
                sum += edge.value
                union(edge.start, edge.end)
            }
        }
        
        // 모든 섬이 연결되어 있는지 확인
        for(i in 2 until island) {
            if(find(parent[i])!=2) {
                sum = -1
            }
        }

        return sum
    }

    bw.write("${kruskal()}")
    bw.flush()
    bw.close()
    br.close()
}