[백준 17472번] [Kotlin] 다리 만들기 2

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

17472번: 다리 만들기 2

 

난이도 : 골드 1
태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리

 

 

설명

DFS / BFS를 사용해 각 섬을 그룹화 해줍니다.

그리고 각 섬의 모든 점들을 저장해 놨다가, 상하좌우로 방향으로 다리를 만들 수 있는지 확인합니다.

상하좌우 방향으로 현재의 섬을 만난다면 다리를 만들 수 없으며, 다른 섬을 만나게 되면 다리를 만들 수 있습니다.

이 다리를 간선으로 취급해 큐에 넣습니다.

 

모든 섬들을 다리로 이어으면서, 다리의 총 길이가 최소가 되어야 하는데,

그룹화된 각 섬들(Node, Vertex)

그리고 그룹화된 각 섬을 이어주는 다리(Edge)

최소 스패닝 트리를 적용하기 아주 좋은 형태가 되었습니다.

 

 

 

소스코드

import java.util.PriorityQueue
import java.util.StringTokenizer


data class Point(val x: Int, val y: Int) // x, y 좌표 저장용 클래스

// 시작 노드, 도착 노드, 간선의 비용
data class Edge(val from: Int, val to: Int, val weight: Int) : Comparable<Edge> {
    override fun compareTo(other: Edge): Int {
        return this.weight - other.weight // 간선 기준으로 정렬
    }
}

lateinit var map: Array<Array<Int>>
lateinit var parent: Array<Int> // 분리 집합에 쓸 부모 저장 배열
var islandIndex = 0 // 각 섬을 그룹화하는데 쓸 각 섬의 index
var n = 0
var m = 0
val islandList = ArrayList<Point>() // 섬들의 모든 좌표
val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)

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

    // 바다 0, 섬 -1로 초기화
    map = Array(n) {
        st = StringTokenizer(readLine())
        Array(m) { if (st.nextToken().toInt() == 0) 0 else -1 }
    }

    // 섬을 그룹화함
    repeat(n) { x ->
        repeat(m) { y ->
            if (map[x][y] == -1) {
                islandIndex++
                groupingIsland(x, y)
            }
        }
    }

    parent = Array(islandIndex + 1) { it }

    val pq = PriorityQueue<Edge>()

    // 섬에서 다른 섬으로 가는 모든 다리를 탐색 (간선을 만드는 과정)
    islandList.forEach { point ->
        for (i in 0 until 4) {
            var bridgeLength = 1

            while (true) {
                val nx = point.x + dx[i] * bridgeLength
                val ny = point.y + dy[i] * bridgeLength

                // 이동헀는데 현재 섬임 -> 다음 케이스로
                if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == map[point.x][point.y]) break

                // 현재 섬이 아니면서, 바다가 아님 => 다른 섬을 만남
                if (map[nx][ny] != 0) {
                    if (bridgeLength >= 3) { // 근데 다리 길이가 2 이상 되야함
                        pq.offer(Edge(map[point.x][point.y], map[nx][ny], bridgeLength - 1)) // 시작 섬, 도착 섬, 다리 길이
                    }
                    break
                }

                bridgeLength++
            }
        }
    }

    var total = 0
    var bridgeCnt = 0
	
    // 최소 스패닝 트리 알고리즘 적용
    while (pq.isNotEmpty()) {
        val target = pq.poll()
        if (union(target.from, target.to)) {
            total += target.weight // 가중치의 합
            bridgeCnt++ // 다리의 개수
        }
    }
	
    // 다리가 (섬 - 1) 개 -> 모든 섬을 이음!
    // 다리가 (섬 - 1) 개 보다 적음 -> 모든 섬을 이을 수 없음. -1 출력
    println(if (bridgeCnt == islandIndex - 1) total else -1)
}

// dfs를 사용해 각 섬을 그룹화함
fun groupingIsland(x: Int, y: Int) {
    map[x][y] = islandIndex
    islandList.add(Point(x, y)) // 섬의 모든 좌표를 리스트에 저장

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

        if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] != -1) continue
        groupingIsland(nx, ny)
    }
}

fun find(x: Int): Int {
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

fun union(x: Int, y: Int): Boolean {
    val nx = find(x)
    val ny = find(y)
    return if (nx != ny) {
        parent[nx] = ny
        true
    } else false
}

 

 

dfs 혹은 bfs를 사용해 각 섬을 그룹화 한 뒤,

섬의 모든 정점에서 다른 섬으로 가는 경로를 탐색하여 (다리가  중간에 꺾이면 안되므로 그냥 십자 방향으로만 탐색)

노드와 엣지를 구하는게 이번 문제의 포인트라 할 수 있습니다.

 

 

후기

굉장히 재밌게 풀었던 문제였습니다.

각 섬을 그룹화하고, 최소 스패닝 트리를 적용시켜야겠다는 생각은 했는데

간선을 어떻게 해야하나 고민하다가 질문게시판을 보고

섬의 모든 좌표에서 십자 모양으로 탐색해 나간 뒤 다른 섬을 만나면 다리를 만들 수 있다는 것이 꽤 인상적이였습니다.