[BOJ][Gold V] 인구 이동 - 16234 (Kotlin)

[Gold V] 인구 이동 - 16234

문제 링크

16234번: 인구 이동

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

문제 설명

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

풀이

접근

인구이동은 하루동안 진행되며 인구 이동이 없을 때 까지 진행된다. 인구이동을 진행하기 위해서는 결국 연합을 찾아야한다. 연합의 정의는 두 국가의 인구수가 L이상 R이하이며 인접해야한다.

결국 문제를 풀기 위해서는 인접한 국가들의 연합을 구해야한다. 상하좌우 4방향으로 bfs또는 dfs와 같은 방법으로 탐색하며 인접 국가들을 찾아볼 수 있겠다.

입력 받기

fun readInts() = readln().split(' ').map { it.toInt() }

fun main() {
    val (n, l, r) = readInts()
    val map = Array(n) { readInts().toIntArray() }
    val lr = l..r
    var day = 0

    ...
}

구조 분해선언으로 3가지 인수를 간단하게 받고, 나머지 NxN 배열을 받아준다. 범위 L~R은 항상 묶여서 사용될 것이므로 IntRange로 미리 묶어주었다.

연합을 저장할 자료구조 : Union

data class Union(
    var sum: Int = 0,
    val list: MutableList<Pair<Int, Int>> = mutableListOf()
)

...

// 연합들의 평탄화 작업을 한다면
listOf(union1, union2, ).forEach { (sum, list) ->
    list.forEach { (y, x) -> 
        map[y][x] = sum / list.size 
    }
}

반복적으로 무언가 하기전에 연합의 정보를 저장할 자료구조가 필요하다. 연합의 필요한 데이터는 각 국가의 좌표값 Pair의 List다. 또한 연합을 구하고, 인구 이동 후 평균값으로 평탄화 작업이 필요하므로 국가들의 인구합을 가지고 있도록 만들었다. 이를 Union이라는 data class로 선언한다.

fun main() 코드

fun main() {
    val (n, l, r) = readInts()
    val map = Array(n) { readInts().toIntArray() }
    val lr = l..r
    var day = 0

    while(true) {
        var open = false
        val visited = Array(n) { Array(n) { false } }
        val unionList = mutableListOf<Union>()

        for(i in 0 until n) {
            for(j in 0 until n) {
                if(visited[i][j]) continue
                visited[i][j] = true

                val union = bfs(map, visited, lr, i, j)
                unionList.add(union)
            }
        }

        unionList.forEach { (sum, list) ->
            if(list.size > 1) open = true
            list.forEach { (y, x) -> map[y][x] = sum / list.size }
        }
        if(!open) break
        day++
    }

    print(day)
}

한번 while 문이 실행되고 나서 인구 이동이 존재했다면 하루가 지나간다.

연합을 구하기 위해서는 N x N 배열을 돌면서 bfs 시작점을 찾는다. visited로 방문 여부를 확인하고 이미 방문한 국가라면 pass하면 된다. bfs를 돌고나면 반환값으로 해당 국가에서 시작되는 연합을 반환한다. 이는 연합리스트 unionList에 추가된다.

연합들을 모두 찾고나서는 평탄화 작업을 해주면 된다. 이때 만약 모든 연합들의 크기가 1이라면 2개이상의 국가가 연합한 경우가 없다는 뜻이고, 이는 즉 인구이동이 없었다는 뜻이다. open 플래그는 true로 설정되지 않고 while문을 탈출한다.

🚧 주의할 점은 연합을 찾고나서 해당 연합에 대해 바로 평탄화 작업을 실시해서는 안된다! 아직 모든 연합을 찾지 않은 경우 국가 인원 수가 동적으로 바뀌어서 잘못된 결과가 나올 수 있다.

BFS : 시작점으로 부터 연합찾기

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

fun bfs(
    map: Array<IntArray>,
    visited: Array<Array<Boolean>>,
    lr: IntRange,
    sy: Int, sx: Int
): Union {
    val union = Union(
        sum = map[sy][sx],
        list = mutableListOf(sy to sx)
    )
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(union.list.last())

    while(queue.isNotEmpty()) {
        val (y, x) = queue.poll()

        for(i in 0..3) {
            val (nx, ny) = x+dx[i] to y+dy[i]

            if(nx !in map.indices || ny !in map.indices) continue
            if(visited[ny][nx]) continue
            if(abs(map[y][x] - map[ny][nx]) !in lr) continue

            visited[ny][nx] = true
            q.add(ny to nx)
            union.sum += map[ny][nx]
            union.list.add(ny to nx)
        }
    }
    return union
}

방문하지 않은 시작점 Pair(sy, sx) 로 부터 시작하는 연합을 찾아야한다.

연합이 되기위한 조건은 2가지이다.

1. 4방향으로 인접할 것
2. 인접 국가간 인구수 차이가 범위 안 일것

추가로 구현하는데 우리가 신경써야하는 추가 조건을 아래와 같다.
3. 이미 방문한 국가가 아닐 것
4. 범위안에 있는 국가일 것

1번 조건을 만족시키기 위해 시작점으로 부터 BFS를 돌며 4방향을 탐색해볼 수 있겠다. 흔히 사용하는 dx, dy 패턴으로 해결하였다. 각 방향에서는 2번 / 3번 / 4번 조건을 모두 만족하는 경우에 큐에 추가하고 연합 데이터를 갱신한다.

큐가 모두 비었다면 탐색이 끝났다는 뜻이고, 찾은 연합을 반환한다.

전체 코드

 

후기

골드 5 문제고, 그래프 탐색을 활용하는 시뮬레이션으로 아주 흔하고 뻔한 문제이다. 그럼에도 불구하고 생각과 다르게 푸는데 많은 시간을 투자했다. 그 이유는 코틀린으로 문제풀이를 한지 얼마되지도 않았고 오랜만에 PS를 하다보니 BFS를 구현하는데에도 잔 실수가 많았다. 문제를 풀고나서 다음날 다시 코드를 정리하며 풀어보았다. 이전의 코드를 보지 않아도 기억이 나기에 바로 풀어버릴 줄 알았는데 다른 실수도 꽤나 나서 금방 풀지는 못했다.

반복적으로 다시 풀면서 쉬운 구현이나 간단한 알고리즘은 눈감고도 짤 수 있을정도로 숙달이 필요하다.

코드를 조금씩 정비하다보니 Kotlin 숏코딩으로 1등을 달성했다. 별 의미있다고는 생각안하지만 처음 1등으로 코드를 올려본게 자랑. kotlin은 sugar sytax가 많아서 코드 짜는 재미있다.

끝