백준 2146번: 다리 만들기 (Kotlin)

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

2146번: 다리 만들기

풀이

바다와 육지로 이루어진 인접 행렬 형태의 그래프가 주어진다. 그러면 모든 섬들을 찾아서, 그 섬들을 잇는 다리 중 가장 짧은 다리를 찾는 문제이다.

 

1. 섬 분류)

섬을 찾기 위해, 붙어있는 육지들을 하나로 묶어서 라벨링을 할 수 있다. 육지 한 점을 시작으로 인접한 곳을 탐색해 나가면서 인접한 곳에는 모두 같은 번호를 붙인다. dfs나 bfs를 사용할 수 있다.

악필 지송..

 

2. 다리 연결)

방법 1) 모든 육지에서부터 한 번씩 경로를 탐색한다

 

이 부분이 까다로운데, 가장 쉽게 생각할 수 있는 방법은 모든 육지를 시작 지점으로 bfs를 수행하는 것이다. 너비 우선으로 탐색하기 때문에 시작 지점과 다른 섬의 육지에 처음 방문하게 됐을 때, 그 이동 거리가 그 지점에서 다른 섬으로 가는 최단 거리가 된다. 모든 지점에서 다른 섬으로 가는 최단 거리를 구하면, 그 중 최소값이 전체에서 가장 짧은 다리가 된다.

 

dfs를 사용하면 어떤 방향을 우선 탐색하느냐에 따라 아래처럼 돌아가는 경로를 먼저 탐색할 수 있다. 그래서 모든 점을 방문해야 하기 때문에 bfs를 사용하는 것이 좋다.

아래, 오른쪽, 위, 왼쪽 순으로 dfs 탐색했을 때

 

시간복잡도는 라벨링 O(n) + 경로 탐색 O(n^3) = O(n^3)이지만, n이 100이라서 괜찮다. 

 

 

방법 2) 육지를 모두 Queue에 넣고, 한 번만 bfs를 수행한다

 

사실 bfs를 사용하면 O(n^2)으로도 경로 탐색을 할 수 있다. 모든 육지를 Queue에 넣고 bfs를 한 번만 수행하는 것이다.

 

방문된 곳은 이동 거리와 어떤 섬에서부터 방문했는지를 표시한다. 그리고 다른 섬 or 다른 섬에서 방문한 바다를 만났을 때, (자신이 이동한 거리) + (다른 섬이 이동한 거리)가 최단 거리가 된다. 모든 지점이 돌아가면서 한 칸씩만 이동하기 때문이다.

방문 처리: 동그라미에서 만나게 된다

이동 거리: 2+1 = 3 

  

(1)방문 표시 + (2)이동 거리 + (3)어떤 섬에서 방문했는지 표시해야 하기 때문에 복잡해서 떠올리기가 어려웠던 것 같다.

나는 그림처럼 방문한 바다에는 시작 지점의 라벨을 저장해서 방문 표시와 어떤 섬에서 시작했는지를 한번에 나타냈는데, 좀 헷갈렸어서 방문 체크를 위한 배열을 따로 사용하는 것도 좋을 것 같다. 이동 거리를 저장하는 배열은 따로 선언했다. 

 

코드 (방법1)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

val dRow = arrayOf(-1, 1, 0, 0)
val dCol = arrayOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val graph = Array(n) { // 그래프 입력 받아서 저장
        StringTokenizer(readLine()).let { st ->
            IntArray(n) { st.nextToken().toInt() }
        }
    }

    var label = 2 // 중복 방문 체크를 위해 2부터 시작
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (graph[i][j] == 1) {
                graph[i][j] = label // 섬 분류
                labelingDfs(graph, i, j, label++)
            }
        }
    }

    var answer = Integer.MAX_VALUE
    for (i in 0 until n) {   // 모든 육지마다 최단 경로 탐색
        for (j in 0 until n) {
            if (graph[i][j] > 1) {
                val copiedGraph = copyGraph(graph) // bfs 수행할 때마다 그래프 복제해야 함
                answer = min(answer, bfs(copiedGraph, i, j))
            }
        }
    }
    print(answer)
}

fun labelingDfs(graph: Array<IntArray>, row: Int, col: Int, label: Int) {
    for (i in 0 until 4) {
        val newRow = row + dRow[i]
        val newCol = col + dCol[i]

        if (newRow in graph.indices && newCol in graph.indices && graph[newRow][newCol] == 1) {
            graph[newRow][newCol] = label // 방문 체크 + 섬 라벨링
            labelingDfs(graph, newRow, newCol, label)
        }
    }
}

fun copyGraph(graph: Array<IntArray>): Array<IntArray>{
    val tempGraph = Array(graph.size){IntArray(graph.size)}
    for (i in graph.indices) {
        for (j in graph.indices){
            tempGraph[i][j] = graph[i][j]
        }
    }

    return tempGraph
}

fun bfs(graph: Array<IntArray>, startRow: Int, startCol: Int): Int {
    var distance = 0
    val label = graph[startRow][startCol]
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    queue.offer(Pair(startRow, startCol))

    while (queue.isNotEmpty()) {
        val size = queue.size 

        // 다리를 한 번씩 모두 늘리면 distance 증가
        repeat(size) {
            val pair = queue.poll()
            val row = pair.first
            val col = pair.second

            for (i in 0 until 4) {
                val newRow = row + dRow[i]
                val newCol = col + dCol[i]

                if (newRow in graph.indices && newCol in graph.indices) {

                    // 방문하지 않았던 바다
                    if (graph[newRow][newCol] == 0) {
                        graph[newRow][newCol] = label
                        queue.offer(Pair(newRow, newCol))
                    }

                    // 바다도 아니고 같은 섬도 아니다 -> 다른 섬에 도착
                    else if (graph[newRow][newCol] != label) {
                        return distance // 경로 이동 횟수 반환
                    }
                }
            }
        }

        distance++
    }

    return Integer.MAX_VALUE // 섬 중앙에서 시작했을 때
}

 

코드 (방법2)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

val dRow = arrayOf(-1, 1, 0, 0)
val dCol = arrayOf(0, 0, -1, 1)
val queue: Queue<Pair<Int, Int>> = LinkedList()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val graph = Array(n) { // 그래프 입력 받아서 저장
        StringTokenizer(readLine()).let { st ->
            IntArray(n) { st.nextToken().toInt() }
        }
    }

    var label = 2 // 중복 방문 체크를 위해 2부터 시작
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (graph[i][j] == 1) {
                graph[i][j] = label // 섬 분류
                labelingDfs(graph, i, j, label++)
            }
        }
    }

    val answer = bfs(graph) // bfs로 최단 경로 탐색
    print(answer)
}

fun labelingDfs(graph: Array<IntArray>, row: Int, col: Int, label: Int) {
    var isEdge = false // 섬의 육지 중 테두리를 찾기 위한 플래그 

    for (i in 0 until 4) {
        val newRow = row + dRow[i]
        val newCol = col + dCol[i]

        if (newRow in graph.indices && newCol in graph.indices && graph[newRow][newCol] != label) {
            if (graph[newRow][newCol] == 0) { // 주변에 바다가 있다 -> 섬의 테두리이다
                isEdge = true
                continue
            }

            graph[newRow][newCol] = label
            labelingDfs(graph, newRow, newCol, label)
        }
    }

    if (isEdge) queue.add(Pair(row, col)) // 섬의 테두리에서만 bfs 시작
}

fun bfs(graph: Array<IntArray>): Int {
    val lengthGraph = Array(graph.size) { IntArray(graph.size) } // 이동 거리 저장하는 배열

    while (queue.isNotEmpty()) {
        val pair = queue.poll()
        val row = pair.first
        val col = pair.second

        for (i in 0 until 4) {
            val newRow = row + dRow[i]
            val newCol = col + dCol[i]

            // 그래프 바깥이거나 해당 라벨에서 이미 방문했던 곳 or 같은 섬이면 건너뛴다 
            if (newRow !in graph.indices || newCol !in graph.indices || graph[newRow][newCol] == graph[row][col]) {
                continue
            }

            // 0이 아니다 -> 다른 라벨이 방문했던 곳 or 다른 라벨의 섬 -> 최단 경로 탐색 완료 
            if (graph[newRow][newCol] != 0) {
                return lengthGraph[row][col] + lengthGraph[newRow][newCol]
            }

            graph[newRow][newCol] = graph[row][col] // 시작점의 라벨로 설정
            lengthGraph[newRow][newCol] = lengthGraph[row][col] + 1 // 이동 거리
            queue.offer(Pair(newRow, newCol))
        }
    }

    return 0
}