[백준 14868번] 문명

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

14868번: 문명

 

난이도 : 플래티넘 4
태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 분리 집합

 

 

설명

문명은 인접한 칸으로 세력을 넓힙니다.

세력을 넓히면서 한 칸을 서로 차지하려 할 때 혹은 서로 맞닿을 때 두 문명은 합쳐집니다.

 

한 칸을 서로 차지하려 할 때는 BFS 탐색 중 쉽게 알 수 있으나,

인접할 경우에는 4방향 BFS를 한 번 더 돌려 확인할 수 있습니다.

 

저는 첫 번째 문명의 경우 map[x][y] = 1,

두 번째 문명의 경우 map[x2][y2] = 2와 같이 맵에 인덱스를 통해 지정해줬는데요.

단순하게 생각했을 때, 두 문명을 합치는 쉬운 방법은 map의 인덱스 정보를 갖게 만들어주는 방법이겠지만,

그렇게 하면 시간초과가 날 것 같습니다.

 

따라서 이번 문제에서는 분리집합과 유니온파인드 알고리즘을 활용할 수 있겠네요.

https://uknowblog.tistory.com/61

[자료구조] 분리 집합(Disjoint set)과 유니온 - 파인드(Union-Find)

 

분리집합에 대해 잘 모르신다면 위 포스팅을 참고해주세요.

 

2개의 문명이 충돌한다면, 서로의 부모 노드가 다를 경우 두 문명은 아직 합쳐지지 않은 문명이며,

두 문명의 부모 노드를 갖게 만들어줍니다.

두 문명의 부모 노드가 같다면, 이미 서로 합쳐진 문명이므로, 넘어갑니다.

 

 

 

 

소스코드

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

lateinit var parent: IntArray

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

fun main() = with(System.`in`.bufferedReader()) {
    val (n, civilCount) = readLine().split(" ").map { it.toInt() }
    parent = IntArray(civilCount + 1) { it }

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

    val map = Array(n) { IntArray(n) { 0 } }
    val q = LinkedList<Node>() as Queue<Node>

    repeat(civilCount) {
        val (x, y) = readLine().split(" ").map { it.toInt() - 1 }
        q.offer(Node(x, y))
        map[x][y] = it + 1
    }

    var unionCivils = 1
    var year = 0

    // 초기 인접 국가 합치기
    q.forEach { (x, y) ->
        for(j in 0 until 4) {
            val nx = x + dx[j]
            val ny = y + dy[j]

            if(nx !in 0 until n || ny !in 0 until n || map[nx][ny] == 0) continue
            if(map[nx][ny] != map[x][y]) {
                if(union(map[x][y], map[nx][ny])) {
                    unionCivils++
                }
            }
        }
    }

    if(unionCivils == civilCount) {
        println(0)
        return
    }

    while (q.isNotEmpty()) {
        repeat(q.size) {
            val cur = q.poll()

            for (i in 0 until 4) {
                val nx = cur.x + dx[i]
                val ny = cur.y + dy[i]
                if (nx !in 0 until n || ny !in 0 until n) continue

                if (map[nx][ny] == 0) {
                    map[nx][ny] = map[cur.x][cur.y]
                    q.offer(Node(nx, ny))
                } else if (map[nx][ny] != map[cur.x][cur.y]) {
                    if (union(map[cur.x][cur.y], map[nx][ny])) {
                        unionCivils++
                    }
                }

                // 인접 국가 합치기
                for (j in 0 until 4) {
                    val nnx = nx + dx[i]
                    val nny = ny + dy[i]

                    if (nnx !in 0 until n || nny !in 0 until n || map[nnx][nny] == 0) continue
                    if (map[nnx][nny] != map[nx][ny]) {
                        if (union(map[nx][ny], map[nnx][nny])) {
                            unionCivils++
                        }
                    }
                }
            }
        }
        year++

        if (unionCivils == civilCount) {
            println(year)
            return
        }
    }
}

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 (px, py) = listOf(find(x), find(y))

    return if (px != py) {
        parent[py] = px
        true
    } else false
}

 

 

 

후기

두 번의 4방향 탐색에 분리집합을 섞어 풀 수 있었던 문제였습니다.

구현과정이 다소 복잡하긴 했지만, 이와 비슷한 문제를 풀어봐서 수월하게 풀 수 있었습니다.

역시 그래프 탐색은 최고야.