[백준 11559번] [Kotlin] Puyo Puyo

 

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

11559번: Puyo Puyo

 

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

 

 

설명

뿌요뿌요 게임 시뮬레이션입니다.

연결된  뿌요의 개수가 4개 이상일 경우 뿌요가 삭제되고,

중력의 영향으로 밑으로 내려온 뒤 4개 이상의 뿌요가 새롭게 생기면

연쇄적으로 해당 뿌요 역시 제거됩니다.

 

뿌요의 상태가 주어졌을 때, 총 몇 번이나 연쇄적으로 뿌요가 삭제되는지 구하는 문제입니다.

 

 

 

접근방법

1. 모든 칸에 대해 DFS/BFS로 인접한 뿌요들을 카운팅한다.

2. 그룹 내 뿌요의 개수가 4개 이상할 때 해당 뿌요들을 삭제한다.

3. 중력을 적용하여 뿌요들을 밑으로 내린다.

4. 삭제된 뿌요가 있다면 1번 과정으로 돌아가며, 삭제된 뿌요가 없다면 종료한다.

 

 

 

소스코드(BFS)

전체 소스코드

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

val dx = intArrayOf(0, 0, -1, 1)
val dy = intArrayOf(-1, 1, 0, 0)
val n = 12
val m = 6

fun main() = with(System.`in`.bufferedReader()) {
    val map = Array(n) { readLine().toCharArray() }
    var ans = 0

    while (true) {
        var isPuyoRemoved = false
        val visited = Array(n) { BooleanArray(m) }

        for (i in 0..<n) {
            for (j in 0..<m) {
                if (map[i][j] == '.' || visited[i][j]) continue
                if (bfs(i, j, visited, map)) isPuyoRemoved = true
            }
        }

        if (!isPuyoRemoved) break
        ans++

        puyoDown(map)
    }

    println(ans)
}

fun bfs(i: Int, j: Int, visited: Array<BooleanArray>, map: Array<CharArray>): Boolean {
    val removeList = ArrayList<Node>()
    val queue = ArrayDeque<Node>()

    queue.add(Node(i, j))
    removeList.add(Node(i, j))
    visited[i][j] = true

    while (queue.isNotEmpty()) {
        val cur = queue.removeFirst()

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

            if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] || map[nx][ny] != map[i][j]) continue
            queue.add(Node(nx, ny))
            removeList.add(Node(nx, ny))
            visited[nx][ny] = true
        }
    }

    if (removeList.size >= 4) {
        removeList.forEach { (x, y) ->
            map[x][y] = '.'
        }
        return true
    }
    return false
}

fun puyoDown(map: Array<CharArray>) {
    for (col in 0..<m) {
        val queue = ArrayDeque<Char>()

        for (row in n - 1 downTo 0) {
            if (map[row][col] == '.') continue
            queue.add(map[row][col])
            map[row][col] = '.'
        }

        var idx = n - 1
        while (queue.isNotEmpty()) {
            map[idx--][col] = queue.removeFirst()
        }
    }
}

 

 

 

BFS

fun bfs(i: Int, j: Int, visited: Array<BooleanArray>, map: Array<CharArray>): Boolean {
    val removeList = ArrayList<Node>()
    val queue = ArrayDeque<Node>()

    queue.add(Node(i, j))
    removeList.add(Node(i, j))
    visited[i][j] = true

    while (queue.isNotEmpty()) {
        val cur = queue.removeFirst()

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

            if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] || map[nx][ny] != map[i][j]) continue
            queue.add(Node(nx, ny))
            removeList.add(Node(nx, ny))
            visited[nx][ny] = true
        }
    }

    if (removeList.size >= 4) {
        removeList.forEach { (x, y) ->
            map[x][y] = '.'
        }
        return true
    }
    return false
}

 

BFS 부분입니다.

상하좌우로 인접한 뿌요들을 찾는 부분인데요.

저 같은 경우, BFS를 위한 Queue(Deque) 하나와,

삭제될 뿌요들을 넣어놓을 List 하나를 사용하였습니다.

 

상하좌우를 탐색하며 같은 뿌요를 만났을 때, 해당 뿌요를 removeList에 넣어주고,

BFS가 종료되었을 때 removeList에 담긴 뿌요의 개수가 4개 이상일 경우,

해당 뿌요들을 모두 지워주고 true(뿌요가 삭제되었음)를 반환합니다.

뿌요가 삭제되지 않았을 경우 false를 반환합니다.

 

 

 

puyoDown

fun puyoDown(map: Array<CharArray>) {
    for (col in 0..<m) {
        val queue = ArrayDeque<Char>()

        for (row in n - 1 downTo 0) {
            if (map[row][col] == '.') continue
            queue.add(map[row][col])
            map[row][col] = '.'
        }

        var idx = n - 1
        while (queue.isNotEmpty()) {
            map[idx--][col] = queue.removeFirst()
        }
    }
}

 

puyoDown은 중력을 적용해 뿌요를 아래로 내리는 역할을 합니다.

각 열에 대해 맨 아래 줄 부터 윗 방향으로 탐색해나가며 큐에 넣어주고 '.'으로 바꾼 뒤,

맨 윗 줄에 도달하면 다시 맨 아랫 줄로 이동하여 하나씩 큐에서 빼며 map에 저장합니다.

 

 

 

아래부터 위로 탐색하며 큐에 원소를 하나씩 넣어주기

 

 

다시 아래부터 위로 탐색하며 큐에서 하나씩 빼기

위와 같은 과정을 통해 중력을 적용해 밑으로 내리는 효과를 볼 수 있습니다.

 

 

 

main

fun main() = with(System.`in`.bufferedReader()) {
    val map = Array(n) { readLine().toCharArray() }
    var ans = 0

    while (true) {
        var isPuyoRemoved = false
        val visited = Array(n) { BooleanArray(m) }

        for (i in 0..<n) {
            for (j in 0..<m) {
                if (map[i][j] == '.' || visited[i][j]) continue
                if (bfs(i, j, visited, map)) isPuyoRemoved = true
            }
        }

        if (!isPuyoRemoved) break
        ans++

        puyoDown(map)
    }

    println(ans)
}

 

main 함수에서는 위 두 메소드를 사용해

아직 탐색하지 않은 모든 점에 대해 bfs를 수행하고,

모든 bfs의 결과가 false(삭제된 뿌요 없음) 일 때 까지 반복합니다.

 

 

 

소스코드 (DFS)

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

val dx = intArrayOf(0, 0, -1, 1)
val dy = intArrayOf(-1, 1, 0, 0)
val n = 12
val m = 6

fun main() = with(System.`in`.bufferedReader()) {
    val map = Array(n) { readLine().toCharArray() }
    var ans = 0

    while (true) {
        var isPuyoRemoved = false
        val visited = Array(n) { BooleanArray(m) }

        for (i in 0..<n) {
            for (j in 0..<m) {
                if (map[i][j] == '.' || visited[i][j]) continue
                val removeList = dfs(i, j, visited, map, ArrayList())
                if (removeList.size >= 4) {
                    isPuyoRemoved = true
                    for (node in removeList) {
                        map[node.x][node.y] = '.'
                    }
                }
            }
        }

        if (!isPuyoRemoved) break
        ans++

        puyoDown(map)
    }

    println(ans)
}

fun dfs(
    x: Int,
    y: Int,
    visited: Array<BooleanArray>,
    map: Array<CharArray>,
    removeList: ArrayList<Node>
): ArrayList<Node> {
    visited[x][y] = true
    removeList.add(Node(x, y))

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

        if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] || map[nx][ny] != map[x][y]) continue
        dfs(nx, ny, visited, map, removeList)
    }

    return removeList
}

fun puyoDown(map: Array<CharArray>) {
    for (col in 0..<m) {
        val queue = ArrayDeque<Char>()

        for (row in n - 1 downTo 0) {
            if (map[row][col] == '.') continue
            queue.add(map[row][col])
            map[row][col] = '.'
        }

        var idx = n - 1
        while (queue.isNotEmpty()) {
            map[idx--][col] = queue.removeFirst()
        }
    }
}

 

위 코드를 DFS로 짠 버전입니다.

태그에 BFS만 있길래, DFS로는 불가능한가? 싶었는데,

DFS로도 별 문제 없이 풀리네요.

 

 

 

후기

큐를 사용해 중력을 적용시켜 뿌요를 내리는 과정은 [백준 12100] 2048(Easy) 을 풀며 알게된 테크닉인데,

꽤나 유용하게 쓰고 있습니다.