[백준/BOJ] 17472번: 다리 만들기2

문제

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

해설

문제를 읽어보면, 크게 3가지 과정을 나눠야하는 것을 알 수 있다.

• 섬을 구분짓는다.
• 섬을 잇는 다리를 놓는다.
• 모든 섬이 연결되었는지 확인 및 다리의 총 길이를 구한다.

단계별로 나가보자.

우선 섬을 구분지어야 한다.

나는 우선 섬으로 표시된 1을 전부 -1로 저장해주었다.

이후 BFS를 사용하여 섬에 번호(1, 2, 3, 4, . . .)를 붙여주었다.

repeat(row) { i ->
    st = StringTokenizer(readLine())
    repeat(col) { j ->
        map[i][j] = st.nextToken().toInt()
        
        if(map[i][j] == 1) map[i][j] = -1
    }
}

var number = 1
for(i in 0 until row) {
    for(j in 0 until col) {
        if(map[i][j] == -1 && !visited[i][j]) {
            islandIndexing(i, j, number)
            number++
        }
    }
}

private fun islandIndexing(y: Int, x: Int, number: Int) {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(y, x))
    map[y][x] = number
    visited[y][x] = true

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.first
        val curX = cur.second

       repeat(4) { i ->
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(isRange(nextY, nextX) && !visited[nextY][nextX] && map[nextY][nextX] == -1) {
                map[nextY][nextX] = number
                visited[nextY][nextX] = true
                que.add(Pair(nextY, nextX))
            }
        }
    }
}

섬을 모두 구분지었으면, 각 섬을 이을 다리를 만들어야 한다.

문제를 보면 알겠지만 다리는 1자로만 놓을 수 있다. 즉 한 방향으로만 놓아야 된다는 것이다.

이는 4중 for문을 이용하면 해결할 수 있다.

한 섬에서 시작하여 다른 섬에 도착했을 때, 다리의 길이가 2 이상이라면 우선순위 큐에 저장해준다.

이는 후에 다리의 총 길이를 구할 때 크루스칼 알고리즘에서 사용하게 된다.

private fun makeBridge(y: Int, x: Int, start: Int) {
    repeat(row) { i -> visited[i].fill(false) }

    val que: Queue<Triple<Int, Int, Int>> = LinkedList()
    for(i in 0 until 4) {
        que.add(Triple(y, x, 0))
        visited[y][x] = true

        while(que.isNotEmpty()) {
            val cur = que.poll()
            val curY = cur.first
            val curX = cur.second
            val len = cur.third

            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(isRange(nextY, nextX) && !visited[nextY][nextX]) {
                if(map[nextY][nextX] != start) {
                    if(map[nextY][nextX] == 0) {
                        que.add(Triple(nextY, nextX, len + 1))
                        visited[nextY][nextX] = true
                    }
                    else {
                        val arrive = map[nextY][nextX]

                        if(len > 1) {
                            pq.add(BridgeInfo(start, arrive, len))
                            break
                        }
                    }
                }
            }
        }
        que.clear()
    }
}

이제 다리도 모두 놓았다.

총 다리 길이를 구해주고, 모든 섬이 연결되있는지 확인해야한다.

크르수칼 알고리즘을 사용한 이유는, 부모 노드를 확인하며 진행하는데 이를 통해 모든 섬이 연결되있는지 확인할 수 있기 때문이다.

private fun kruskal(number: Int): Int {
    parent = IntArray(number) { i -> i }
    var totalLength = 0

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val from = cur.from
        val to = cur.to
        val len = cur.len

        if(find(from) != find(to)) {
            union(from, to)
            totalLength += len
        }
    }

    var allConnect = true
    for(i in 2 until number) {
        if(find(parent[i]) != 1) allConnect = false
    }

    return if(allConnect) totalLength
    else 0
}

private fun union(a: Int, b: Int) {
    val aRoot = find(a)
    val bRoot = find(b)

    if(aRoot < bRoot) parent[bRoot] = aRoot
    else parent[aRoot] = bRoot
}

private fun find(island: Int): Int {
    if(parent[island] != island) return find(parent[island])
    return parent[island]
}

모든 섬이 연결되있지 않다면 0을 반환하도록 한다.

마지막으로 main 함수로 돌아가 결과값이 0이라면 -1을 출력, 이외의 값이라면 그 값을 출력해주면 된다.

전체적인 코드는 아래를 확인하자.

코드

import java.util.*

data class BridgeInfo(val from: Int, val to: Int, val len: Int): Comparable<BridgeInfo> {
    override fun compareTo(other: BridgeInfo): Int = len - other.len
}

private lateinit var map: Array<IntArray>
private lateinit var visited: Array<BooleanArray>
private lateinit var parent: IntArray
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private val pq = PriorityQueue<BridgeInfo>()
private var row = 0
private var col = 0

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    row = st.nextToken().toInt()
    col = st.nextToken().toInt()

    map = Array(row) { IntArray(col) }
    visited = Array(row) { BooleanArray(col) }

    repeat(row) { i ->
        st = StringTokenizer(readLine())
        repeat(col) { j ->
            map[i][j] = st.nextToken().toInt()

            if(map[i][j] == 1) map[i][j] = -1
        }
    }

    var number = 1
    for(i in 0 until row) {
        for(j in 0 until col) {
            if(map[i][j] == -1 && !visited[i][j]) {
                islandIndexing(i, j, number)
                number++
            }
        }
    }

    for(i in 0 until row) {
        for(j in 0 until col) {
            if(map[i][j] != 0) {
                makeBridge(i, j, map[i][j])
            }
        }
    }


    val ans = kruskal(number)

    if(ans == 0) println(-1)
    else println(ans)
}

private fun islandIndexing(y: Int, x: Int, number: Int) {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(y, x))
    map[y][x] = number
    visited[y][x] = true

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.first
        val curX = cur.second

       repeat(4) { i ->
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(isRange(nextY, nextX) && !visited[nextY][nextX] && map[nextY][nextX] == -1) {
                map[nextY][nextX] = number
                visited[nextY][nextX] = true
                que.add(Pair(nextY, nextX))
            }
        }
    }
}

private fun makeBridge(y: Int, x: Int, start: Int) {
    repeat(row) { i -> visited[i].fill(false) }

    val que: Queue<Triple<Int, Int, Int>> = LinkedList()
    for(i in 0 until 4) {
        que.add(Triple(y, x, 0))
        visited[y][x] = true

        while(que.isNotEmpty()) {
            val cur = que.poll()
            val curY = cur.first
            val curX = cur.second
            val len = cur.third

            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(isRange(nextY, nextX) && !visited[nextY][nextX]) {
                if(map[nextY][nextX] != start) {
                    if(map[nextY][nextX] == 0) {
                        que.add(Triple(nextY, nextX, len + 1))
                        visited[nextY][nextX] = true
                    }
                    else {
                        val arrive = map[nextY][nextX]

                        if(len > 1) {
                            pq.add(BridgeInfo(start, arrive, len))
                            break
                        }
                    }
                }
            }
        }
        que.clear()
    }
}

private fun kruskal(number: Int): Int {
    parent = IntArray(number) { i -> i }
    var totalLength = 0

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val from = cur.from
        val to = cur.to
        val len = cur.len

        if(find(from) != find(to)) {
            union(from, to)
            totalLength += len
        }
    }

    var allConnect = true
    for(i in 2 until number) {
        if(find(parent[i]) != 1) allConnect = false
    }

    return if(allConnect) totalLength
    else 0
}

private fun union(a: Int, b: Int) {
    val aRoot = find(a)
    val bRoot = find(b)

    if(aRoot < bRoot) parent[bRoot] = aRoot
    else parent[aRoot] = bRoot
}

private fun find(island: Int): Int {
    if(parent[island] != island) return find(parent[island])
    return parent[island]
}

private fun isRange(y: Int, x: Int): Boolean = (y in 0 until row && x in 0 until col)