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

문제

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

2146번: 다리 만들기

해설

문제를 해결하기 위한 과정을 생각해보자.

1. 섬을 구분한다.
2. 각각의 섬을 연결할 때, 최소의 다리 수로 이어질 수 있도록 한다.

크게 두 가지로 나눌 수 있다.

 

1번 과정부터 보자.

입력에 육지인 부분은 1로 들어온다.

나는 섬을 1, 2, 3의 번호로 나눌 것이기 때문에, 1이 들어오면 -1로 저장을 해주었다.

모든 입력을 받은 후, 아직 방문하지 않은 육지인 곳이 있다면 bfs를 수행시켜준다.

dfs로도 할 수 있지만, 나는 bfs가 더 익숙하여 bfs로 진행하였다.

bfs 수행 과정은 상하좌우로 탐색을 하며 -1(육지)인 곳을 섬으로 체크해주는 것이다.

이 과정이 끝나면 섬이 1, 2, 3, ... 의 번호로 구분이 끝날 것이다.

 

이제 2번 과정을 보자.

이 과정에서도 bfs를 수행할 것이다.

우리는 한 육지에서 또 다른 육지 사이의 바다를 연결해야 한다.

따라서 맵을 처음부터 다시 반복하면서 바다가 아닐 때, bfs를 수행할 것이다.

이 때, 방문 여부를 체크하던 배열을 초기화 해줘야한다. 1번 과정에서 섬을 구분하는데, visited 배열을 사용하였기 때문이다. 또는 새로 선언하여도 된다.

bfs를 수행하면서 현재 위치가 0(바다)이라면 방문여부를 체크해주고, 큐에 현재 위치와 다리의 길이 + 1을 넣어준다.

탐색을 하다가 0이 아니며 처음 시작했던 섬과 다른 번호에 도착했다면, 다리가 다 놓아진 것이다.

따라서 이전에 놓았던 다리보다 길이가 작다면 다리의 길이를 저장한 변수를 갱신해주면 된다.

 

코드를 보면 좀 더 쉽게 이해할 수 있을 것이다.

코드

import java.util.*

private var n = 0
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var len = Int.MAX_VALUE
private lateinit var map: Array<IntArray>
private lateinit var visited: Array<BooleanArray>

data class Pos(val y: Int, val x: Int, val dist: Int)

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    map = Array(n) { IntArray(n) }
    visited = Array(n) { BooleanArray(n) }

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

    // 섬 번호 구분
    var land = 1
    repeat(n) { i ->
        repeat(n) { j ->
            if(map[i][j] == -1 && !visited[i][j]) {
                compareLand(i, j, land)
                land++
            }
        }
    }

    // 다리 놓기
    repeat(n) { i ->
        repeat(n) { j ->
            if(map[i][j] != 0) putBridge(i, j)
        }
    }

    println(len)
}

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

    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(checkRange(nextY, nextX)) {
                if(!visited[nextY][nextX] && map[nextY][nextX] == -1) {
                    visited[nextY][nextX] = true
                    map[nextY][nextX] = land
                    que.add(Pair(nextY, nextX))
                }
            }
        }
    }
}

private fun putBridge(y: Int, x: Int) {
    val que: Queue<Pos> = LinkedList()
    que.add(Pos(y, x, 0))
    for(i in 0 until n) visited[i].fill(false) // visited 배열 초기화
    visited[y][x] = true

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.y
        val curX = cur.x
        val curDist = cur.dist

        if(len <= curDist) return

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

            if(checkRange(nextY, nextX) && !visited[nextY][nextX]) {
                if(map[nextY][nextX] == 0) {
                    visited[nextY][nextX] = true
                    que.add(Pos(nextY, nextX, curDist + 1))
                }
                else if(map[nextY][nextX] != map[y][x]) len = minOf(len, cur.dist)
            }
        }
    }
}

private fun checkRange(y: Int, x: Int): Boolean = (y in 0 until n && x in 0 until n)