[백준 21609번] [Kotlin] 상어중학교

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

21609번: 상어 중학교

난이도 : 골드 2
태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색

 

 

설명

삼성 기출문제로도 유명한 상어 시리즈 중 상어 중학교 입니다.

다른 상어 시리즈와 마찬가지로 시뮬레이션 + 그래프(탐색 및 백트래킹) + 배열 뒤집기가 인상적이였던 문제였습니다.

 

 

계속 테스트케이스가 다르게 나왔는데,

시뮬레이션 문제 특성 상 한 회차당 맵이 어떻게 바뀌는지 확인해야 하기 때문에

엑셀로 하나하나 다 체크해보며 풀었던 문제였습니다...ㅠㅠ

위 사진은 예제 2번인데, 뒤늦게 2번째 턴에서 틀린 걸 찾았습니다. (4 그룹이 지워져야 합니다)

 

 

 

소스코드

package baekjoon.gold.g2.상어중학교

import java.util.*

data class Node(val x: Int, val y: Int)
data class Group(var rainbowBlockCnt: Int, var standardX: Int, var standardY: Int, var groupSize: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    var ans = 0
    val map = Array(n) { readLine().split(" ").map { it.toInt() }.toTypedArray() }
    val visited = Array(n) { BooleanArray(n) }
    val dx = intArrayOf(-1, 1, 0, 0)
    val dy = intArrayOf(0, 0, -1, 1)

    while (true) {
        visited.forEach { it.fill(false) }
        val groupList = mutableListOf<Group>()

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

                val initialColor = map[i][j]

                val q = LinkedList<Node>() as Queue<Node>
                q.add(Node(i, j))
                visited[i][j] = true
                val group = Group(0, i, j, 1)

                val rainbowBlocks = mutableListOf<Node>()

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

                    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 n ||
                            map[nx][ny] == -1 ||
                            map[nx][ny] == -2 ||
                            map[nx][ny] != 0 && map[nx][ny] != initialColor ||
                            visited[nx][ny]
                        ) continue

                        if (map[nx][ny] == 0) {
                            rainbowBlocks.add(Node(nx, ny))
                            group.rainbowBlockCnt++
                        } else {
                            if (nx < group.standardX) {
                                group.standardX = nx
                                group.standardY = ny
                            } else if (nx == group.standardX && ny < group.standardY) {
                                group.standardY = ny
                            }
                        }

                        q.offer(Node(nx, ny))
                        visited[nx][ny] = true
                        group.groupSize++
                    }
                }

                if (group.groupSize >= 2) {
                    groupList.add(group)
                }

                rainbowBlocks.forEach { visited[it.x][it.y] = false }
            }
        }
        if (groupList.isEmpty()) break

        /*
            1. 그룹의 크기가 가장 큰 순
            2. 무지개 블록의 수가 가장 많은 순
            3. 행이 가장 큰 순
            4. 열이 가장 큰 순
         */
        groupList.sortWith(compareBy({ -it.groupSize }, { -it.rainbowBlockCnt }, { -it.standardX }, { -it.standardY }))

        val selectedGroup = groupList.first()
        val q = LinkedList<Node>() as Queue<Node>
        q.add(Node(selectedGroup.standardX, selectedGroup.standardY))

        val initialColor = map[selectedGroup.standardX][selectedGroup.standardY]
        map[selectedGroup.standardX][selectedGroup.standardY] = -2
        var blockCnt = 1

        while (q.isNotEmpty()) {
            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 ||
                    map[nx][ny] != 0 && map[nx][ny] != initialColor
                ) continue

                blockCnt++
                map[nx][ny] = -2
                q.offer(Node(nx, ny))
            }
        }

        ans += blockCnt * blockCnt

        gravity(map)


        // 블록 반시계 방향으로 90도 회전
        val rotatedMap = Array(n) { Array(n) { -2 } }
        for (i in 0 until n) {
            for (j in 0 until n) {
                rotatedMap[n - 1 - j][i] = map[i][j]
            }
        }

        // 블록 내리기
        gravity(rotatedMap)

        for (i in 0 until n) {
            for (j in 0 until n) {
                map[i][j] = rotatedMap[i][j]
            }
        }
    }

    println(ans)
}

fun gravity(map: Array<Array<Int>>) {
    val n = map.size

    for (i in n - 2 downTo 0) {
        for (j in 0 until n) {
            if (map[i][j] == -1) continue

            var nx = i
            while (nx + 1 < n && map[nx + 1][j] == -2) {
                map[nx + 1][j] = map[nx][j]
                map[nx][j] = -2
                nx++
            }
        }
    }
}

 

 

Group Class

data class Group(var rainbowBlockCnt: Int, var standardX: Int, var standardY: Int, var groupSize: Int)

 

그룹은 각 블록 그룹의 데이터를 담을 클래스입니다.

무지개 블록 개수, 기준 블록 x, y 좌표, 그룹의 사이즈를 담고 있습니다.

 

 

 

각 블록 그룹화 (BFS)

visited.forEach { it.fill(false) }
val groupList = mutableListOf<Group>()

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

        val initialColor = map[i][j]

        val q = LinkedList<Node>() as Queue<Node>
        q.add(Node(i, j))
        visited[i][j] = true
        val group = Group(0, i, j, 1)

        val rainbowBlocks = mutableListOf<Node>()

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

            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 n ||
                    map[nx][ny] == -1 ||
                    map[nx][ny] == -2 ||
                    map[nx][ny] != 0 && map[nx][ny] != initialColor ||
                    visited[nx][ny]
                ) continue

                if (map[nx][ny] == 0) {
                    rainbowBlocks.add(Node(nx, ny))
                    group.rainbowBlockCnt++
                } else {
                    if (nx < group.standardX) {
                        group.standardX = nx
                        group.standardY = ny
                    } else if (nx == group.standardX && ny < group.standardY) {
                        group.standardY = ny
                    }
                }

                q.offer(Node(nx, ny))
                visited[nx][ny] = true
                group.groupSize++
            }
        }

        if (group.groupSize >= 2) {
            groupList.add(group)
        }

        rainbowBlocks.forEach { visited[it.x][it.y] = false }
    }
}
if (groupList.isEmpty()) break

 

각 블록을 그룹화하는 부분입니다. BFS를 사용하였습니다.

주의할 점은 무지개 블록의 경우, 매 탐색이 끝날 때 마다 다시 방문체크를 false로 처리해야 한다는 점 입니다.

해당 블록 그룹 뿐 아니라 다른 블록 그룹에서도 사용할 수 있기 때문이죠.

 

매 탐색을 하면서 각 그룹을 정렬하기 위해

무지개 블록의 개수, 블록 그룹의 개수, 기준 블록의 (x, y) 좌표를 업데이트 시킵니다.

 

모든 블록 그룹은 그룹을 이루고 있는 블럭의 크기가 2 이상이여야 하므로, 2개 이상인 그룹만 그룹 리스트에 넣어줍니다.

 

모든 점에서 탐색 및 그룹화를 진행하였음에도, 그룹 리스트가 비어있을 경우엔

더 이상 그룹을 형성할 수 없음을 의미하므로, 무한 반복 문을 탈출합니다.

 

 

블록 그룹 삭제

/*
    1. 그룹의 크기가 가장 큰 순
    2. 무지개 블록의 수가 가장 많은 순
    3. 행이 가장 큰 순
    4. 열이 가장 큰 순
 */
groupList.sortWith(compareBy({ -it.groupSize }, { -it.rainbowBlockCnt }, { -it.standardX }, { -it.standardY }))

val selectedGroup = groupList.first()
val q = LinkedList<Node>() as Queue<Node>
q.add(Node(selectedGroup.standardX, selectedGroup.standardY))

val initialColor = map[selectedGroup.standardX][selectedGroup.standardY]
map[selectedGroup.standardX][selectedGroup.standardY] = -2
var blockCnt = 1

while (q.isNotEmpty()) {
    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 ||
            map[nx][ny] != 0 && map[nx][ny] != initialColor
        ) continue

        blockCnt++
        map[nx][ny] = -2
        q.offer(Node(nx, ny))
    }
}

 

1. 그룹의 크기가 가장 큰 순
2. 무지개 블록의 수가 가장 많은 순
3. 행이 가장 큰 순
4. 열이 가장 큰 순

위 기준으로 정렬한 다음, 가장 앞에 있는 블록 그룹을 찾습니다.

그리고 BFS를 한 번 더 돌려 해당 그룹을 제거합니다.

 

 

 

중력 적용

fun gravity(map: Array<Array<Int>>) {
    val n = map.size

    for (i in n - 2 downTo 0) {
        for (j in 0 until n) {
            if (map[i][j] == -1) continue

            var nx = i
            while (nx + 1 < n && map[nx + 1][j] == -2) {
                map[nx + 1][j] = map[nx][j]
                map[nx][j] = -2
                nx++
            }
        }
    }
}

 

맵을 입력받아 중력을 적용하는 부분입니다.

단순히 한 칸씩 움직여 더 이상 움직일 수 없을 때 까지 반복하였습니다.

 

 

 

맵 반시계 회전

// 블록 반시계 방향으로 90도 회전
val rotatedMap = Array(n) { Array(n) { -2 } }
for (i in 0 until n) {
    for (j in 0 until n) {
        rotatedMap[n - 1 - j][i] = map[i][j]
    }
}

 

맵을 반시계 방향으로 90도 회전하는 부분입니다.

상어 시리즈에서 맵 회전이 많이 나온 것 같은데,

위와 같은 방법으로 맵을 회전시켰습니다.

 

 

 

후기

문제의 조건이 생각보다 많아서 어디서 틀린건지 찾기 위해 엑셀로 일일히 그리면서 푼 문제였습니다...

시간을 좀 들여 결국 풀긴 풀었는데, 제한된 시간 안에 풀어야 하는 실제 코딩테스트에서 이런 문제가 나온다면, 꽤 당황스러울거 같네요 🤣