[백준 2146번] [Kotlin] 다리 만들기

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

2146번: 다리 만들기

 

난이도 : 골드 3
태그 : 그래프이론, 그래프탐색, 너비우선탐색

 

 

설명

앞서 포스팅한 다리만들기 2와 비슷하지만, 1이기 때문에 2보단 쉽습니다.

여러개의 섬이 있을 때, 두 섬을 하나의 다리로 이으면 되기 때문입니다.

 

접근방법

1) DFS / BFS로 모든 섬을 그룹화한다. 이 때, 모든 섬의 좌표를 저장해놓는다.

2) 1번 과정에서 저장해놓은 각 섬의 모든 좌표를 기준으로 BFS를 수행한다.

2-1) BFS 수행 중, 시작 지점과 같은 섬을 만났을 경우, 다음 케이스로 넘어간다. 같은 섬 끼리는 다리를 연결하지 않기 때문이다.

2-2) BFS 수행 중, 다른 섬을 만났을 경우 탐색을 종료한다. 첫 시작지점과 종료지점의 거리가 다리의 길이가 되며, 매 번 다리의 최솟값을 초기화한다.

3) 각 섬의 모든 좌표에서 BFS가 끝나면 다리의 최소 길이를 출력한다.

 

처음에는 연산량이 좀 많을 것 같아 괜찮나 싶었지만,

n의 최대 크기가 100밖에 되지 않아 충분히 시간 안에 통과가 가능할 것으로 판단했습니다.

 

 

 

소스코드

import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer

data class Node(val x: Int, val y: Int)

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

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

    val map = Array(n) {
        val st = StringTokenizer(readLine())
        Array(n) { st.nextToken().toInt() }
    }

    var visited = Array(n) { Array(n) { false } }
    
    // 섬의 모든 좌표를 저장해 놓을 큐
    val islands = LinkedList<Node>() as Queue<Node>

	// 섬을 그룹화할때, 섬의 번호
    var groupIndex = 2

    // 모든 섬을 그룹화 (BFS)
    repeat(n) { x ->
        repeat(n) { y ->
            if (!visited[x][y] && map[x][y] == 1) {
                // BFS
                visited[x][y] = true
                map[x][y] = groupIndex
                islands.add(Node(x, y))

                val q = LinkedList<Node>() as Queue<Node>
                q.offer(Node(x, y))

                while (q.isNotEmpty()) {
                    val target = q.poll()

                    for (i in 0 until 4) {
                        val nx = target.x + dx[i]
                        val ny = target.y + dy[i]

                        if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] || map[nx][ny] != 1) continue

                        q.offer(Node(nx, ny))
                        visited[nx][ny] = true
                        islands.add(Node(nx, ny))
                        map[nx][ny] = groupIndex
                    }
                }
                groupIndex++
            }
        }
    }

    var minLength = Int.MAX_VALUE

    while (islands.isNotEmpty()) {
        // 각 섬의 모든 좌표에서 BFS 수행
        val startPoint = islands.poll()
        val q = LinkedList<Node>() as Queue<Node>

        val visited = Array(n) { Array(n) { -1 } }
        visited[startPoint.x][startPoint.y] = 0

        q.offer(Node(startPoint.x, startPoint.y))

        // while 문 라벨링
        bfs@ while (q.isNotEmpty()) {
            val target = q.poll()

            for (i in 0 until 4) {
                val nx = target.x + dx[i]
                val ny = target.y + dy[i]

                if (nx !in 0 until n || ny !in 0 until n || map[nx][ny] == map[startPoint.x][startPoint.y] || visited[nx][ny] != -1) continue

                // 시작 섬과 같지 않으면서 바다가 아님 -> 새로운 섬을 만남
                if (map[nx][ny] != 0) {
                    minLength = minOf(minLength, visited[target.x][target.y])
                    break@bfs // 라벨링한 반복문을 탈출
                }

                q.offer(Node(nx, ny))
                visited[nx][ny] = visited[target.x][target.y] + 1
            }
        }
    }

    println(minLength)
}

 

 

코드 상에서 BFS가 총 두 번 나타납니다.

섬을 그룹화하는데 한 번, 섬의 모든 좌표에서 다른 섬 까지의 최단경로를 찾는데 한 번.

물론, 섬을 그룹화할 때는 DFS를 써도 무방합니다.

 

 

후기

다리만들기 2를 먼저 풀고와서 그런지, 어렵지 않게 풀 수 있었던 것 같습니다.

역시 DFS / BFS는 언제 해도 재밌는 거 같아요.