2146번: 다리 만들기 - Kotlin (BFS)

2146번: 다리 만들기

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

나의 풀이

이 문제는 BFS를 사용해야 하는 문제이다. 이 문제는 3가지로 나눠서 풀어야 겠다고 생각이 바로 들었다. 

 

1. 섬을 찾는다.
2. 가장 짧은 다리를 찾는다.
3. 다리의 길이 출력

섬을 찾는 것은 브루트포스와 BFS를 이용한 방식으로 2차원 배열을 전부 탐색하면서 숫자로 넣어줬다. 이 과정은 다음과 같다.

 

 

 왼쪽을 오른쪽으로 바꾸면 각 섬이 나타나게 된다. 가장 짧은 다리를 찾는 방법도 비슷하다. 0이 아닌 위치에서 자신의 숫자를 제외한 숫자로만 이동 가능하게 만들고 다른 섬이 나타나면 거기까지의 방문 횟수를 저장하고 정답에 넣어주는 방식을 취했다. 다만 전체를 다 돌리면 시간이 초과됨으로 조건을 몇 개 추가해줘서 시간 초과를 막아줬다.

 

import java.util.LinkedList
import java.util.Queue
import kotlin.math.min

val dx = arrayOf(1, 0, 0, -1)
val dy = arrayOf(0, 1, -1, 0)

var n = 0
lateinit var map : Array<IntArray>
lateinit var visited : Array<BooleanArray>

var ans = Int.MAX_VALUE

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()

    map = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }
    visited = Array(n) { BooleanArray(n) }

    for (i in 0 until n) {
        for (j in 0 until n) {
            if (map[i][j] == 1 && !visited[i][j]) {
                findLand(i, j)
            }
        }
    }

    for (i in 0 until n) {
        for (j in 0 until n) {
            if (map[i][j] != 0) {
                findBridge(i, j, map[i][j])
            }
        }
    }

    println(ans)
}

var landNum = 1
fun findLand(nowX: Int, nowY: Int) {
    val queue : Queue<Pair<Int, Int>> = LinkedList()
    queue.add(nowX to nowY)
    visited[nowX][nowY] = true
    map[nowX][nowY] = landNum

    while (queue.isNotEmpty()) {
        val (x, y) = queue.poll()

        for (i in 0 until 4) {
            val tempX = x + dx[i]
            val tempY = y + dy[i]

            if (tempX in 0 until n &&
                tempY in 0 until n &&
                !visited[tempX][tempY] &&
                map[tempX][tempY] == 1) {
                visited[tempX][tempY] = true
                queue.add(tempX to tempY)
                map[tempX][tempY] = landNum
            }
        }
    }

    landNum++
}

data class Bridge(val x: Int, val y: Int, val cnt: Int)
fun findBridge(nowX: Int, nowY: Int, land: Int) {
    val queue : Queue<Bridge> = LinkedList()
    val visitedSea = Array(n) { BooleanArray(n) }
    queue.add(Bridge(nowX, nowY, 0))
    visitedSea[nowX][nowY] = true

    while (queue.isNotEmpty()) {
        val (x, y, cnt) = queue.poll()

        if (cnt - 1 >= ans) {
            return
        }

        if (map[x][y] != 0 && map[x][y] != land) {
            ans = min(ans, cnt - 1)
            return
        }

        for (i in 0 until 4) {
            val tempX = x + dx[i]
            val tempY = y + dy[i]

            if (tempX in 0 until n &&
                tempY in 0 until n &&
                !visitedSea[tempX][tempY] &&
                map[tempX][tempY] != land) {
                visitedSea[tempX][tempY] = true
                queue.add(Bridge(tempX, tempY, cnt + 1))
            }
        }
    }
}