[백준 16920번] [Kotlin] 확장 게임

 

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

16920번: 확장 게임

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

 

 

설명

각 플레이어 i는 한 턴에 S(i) 거리 만큼 확장을 할 수 있습니다.

각 플레이어 별로, 그리고 한 싸이클씩 그래프 탐색을 진행하는게 포인트라 할 수 있습니다.

 

예제중 하나를 가져와봤습니다.

초기 상태가 아래와 같고, 플레이어 1이 2칸, 플레이어 2가 1칸씩 움직일 수 있는 경우입니다.

1..1
....
....
...2

 

 

1회차 확장이 끝나면 아래와 같아집니다.

1회차

플레이어1 확장
1111
1111
1..1
...2

플레이어2 확장
1111
1111
1..1
..22

 

 

 

2회차 확장이 끝나면 아래와 같아집니다.

2회차

플레이어1 확장
1111
1111
1111
1122

플레이어2 확장
확장할 칸이 없으므로 종료

 

 

이번 문제의 핵심은 BFS를 각 플레이어 별로 돌리는 것입니다.

따라서 저는 각각의 플레이어 수 p에 따라 BFS를 위한 p개의 큐를 만들어줬고,

한 플레이어씩 돌아가며 BFS를 수행합니다.

단 BFS를 수행할 때, 또 다시 사이클별로 BFS를 돌려야 하는데,

이는 각 플레이어의 이동 가능 거리가 다르기 때문입니다.

 

BFS를 시작할 때, 큐의 사이즈를 받아와 해당 사이즈만큼만 BFS를 수행하여,

한 사이클 단위로 BFS를 수행할 수 있습니다.

 

위 과정을 모든 플레이어가 더 이상 확장을 할 수 없을 때 까지 반복합니다.

 

 

 

소스코드

package baekjoon.gold.g2

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

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m, p) = readLine().split(" ").map { it.toInt() }
    val castleCnt = Array(p + 1) { 0 }
    val distance = Array(p + 1) { 0 }

    val qList = Array(p + 1) { ArrayDeque<Node>() }

    readLine().split(" ").map { it.toInt() }.forEachIndexed { index, i -> distance[index + 1] = i }

    val map = Array(n) { Array(m) { 0 } }

    for (i in 0 until n) {
        val input = readLine()
        for (j in 0 until m) {
            if (input[j] == '.') map[i][j] = 0
            else if (input[j] == '#') map[i][j] = -1
            else {
                map[i][j] = input[j].digitToInt()
                castleCnt[map[i][j]]++
                qList[map[i][j]].add(Node(i, j))
            }
        }
    }

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

    var endCnt = 0
    val isEnd = Array(p + 1) { false }

    while (true) {
        if (endCnt == p) break

        for (playerNumber in 1..p) {
            if (qList[playerNumber].isEmpty()) {
                if (!isEnd[playerNumber]) {
                    isEnd[playerNumber] = true
                    endCnt++
                }
                continue
            }

            for (i in 0 until distance[playerNumber]) {
                if (qList[playerNumber].isEmpty()) break

                for(j in 0 until qList[playerNumber].size) {
                    val cur = qList[playerNumber].removeFirst()

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

                        if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] != 0) continue
                        map[nx][ny] = playerNumber
                        castleCnt[playerNumber]++
                        qList[playerNumber].add(Node(nx, ny))
                    }
                }
            }
        }
    }

    println(castleCnt.slice(1..p).joinToString(" "))
}

 

 

 

후기

BFS를 삶아먹고 구워먹는 테크닉이 필요했던 문제였습니다.

최근에 조금 나른했는데, 그래프 탐색을 하니 기운이 좀 나는군요.