[백준] 11559 Puyo Puyo

 

🔒 문제

🧠 아이디어

가로 6, 세로 12를 갖는 테트리스 판의 일종이다

 

우선 4개 이상의 뿌요 조각이 인접해있을 때만 '.'으로 대치한다.

+ '.'으로 대치된 조각이 있으면 아래로 뿌요조각을 당겨야한다.

 

 

뿌요 조각을 당기는 아이디어가 핵심이다.

세로 막대를 의미하는 LinkedList 를 미리 6개 생성해두고 '.'만을 모두 제거해 남은 뿌요 조각을 뿌요판에 붙여넣는다.

 

또, 판 크기 자체가 12 * 6 == 72회로 작으므로 전체 판을 매번 긁어도 시간 초과하지 않겠다는 직관을 가지고 풀이했다.

하나의 뿌요조각이 다음 단계로 이어지려면 매번 4조각씩 해도 총 18라운드가 최대다.

72 * 72 * 18 => 약 10만 으로 절대 시간초과가 나지않는다.

 

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

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

private fun bfs(startRowIdx: Int, startColIdx: Int, map: Array<CharArray>, visited: Array<BooleanArray>) : Boolean {
    visited[startRowIdx][startColIdx] = true
    val startColor = map[startRowIdx][startColIdx]
    val sameColorPoints = LinkedList<IntArray>()

    val queue : Queue<IntArray> = LinkedList<IntArray>()
    queue.add(intArrayOf(startRowIdx, startColIdx))

    while (queue.isNotEmpty()) {
        val (curRow, curCol) = queue.poll()
        sameColorPoints.add(intArrayOf(curRow, curCol))

        for (idx in dx.indices) {
            val nextRow = curRow + dx[idx]
            val nextCol = curCol + dy[idx]

            if (nextRow < 0 || nextCol < 0 || nextRow >= map.size || nextCol >= map[0].size) continue
            if (visited[nextRow][nextCol]) continue
            if (map[nextRow][nextCol] != startColor) continue

            queue.add(intArrayOf(nextRow, nextCol))
            visited[nextRow][nextCol] = true
        }
    }

    if (sameColorPoints.size >= 4) {
        // break
        sameColorPoints.forEach { (row,col)->
            map[row][col] = '.'
        }
        return true
    }

    return false

}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val map = Array(12){CharArray(6)}

    for (i in 0 .. 11) {
        map[i] = bufferedReader.readLine().toCharArray()
    }

    val visited = Array(12){BooleanArray(6)}

    val emptyLine = charArrayOf('.', '.', '.', '.', '.', '.')


    var answer = 0

    while (true) {
        // index: column, value: charArray linked list (세로 줄)
        val puyoColumnList = Array(6){ LinkedList<Char>() }

        var existBreak = false
        // 매 라운드를 우측 하단부터 좌측 상단까지
        for (row in map.indices.reversed()) {
            for (col in map[row].indices.reversed()) {
                if (!visited[row][col] && map[row][col] != '.') {
                    // 깨질 필요가 있는 것들은 '.' 으로 색칠됨.
                    if(bfs(row, col, map, visited)) existBreak = true
                }
            }
        }

        if (!existBreak) break
        else answer++

        visited.forEach { Arrays.fill(it, false) }

        // 아래에서 위로 한칸씩, 맨 왼쪽칸부터 오른쪽으로
        for (col in map[0].indices) {
            for (row in map.indices.reversed()) {
                puyoColumnList[col].add(map[row][col])
            }
        }

        // pull down
        for (puyoColumn in puyoColumnList) {
            puyoColumn.removeIf { it == '.' }
        }

        // pull down 처리 된 puyoColumn 의 상태를 map 에 붙여넣기.
        // puyoColumn 에는 색상 조각만 존재하므로 size 만큼 붙여넣고 나머지는 전부 '.'으로 채워넣기
        for (row in map.indices) {
            map[row] = emptyLine.copyOf()
        }

        // . 제거하고 남은 것 덮어쓰기
        for (col in map[0].indices) {
			맨 끝칸부터 붙여넣음.
            var rowIdx = 11
            for (puyoColumn in puyoColumnList[col]) {
                map[rowIdx--][col] = puyoColumn
            }
        }

    }

    print(answer)

}

 

 

🧠 아이디어 2

모든 뿌요 조각들이 index 의 맨 끝에 위치해있어 index 컨트롤을 끝에서부터 (가로5, 4, 3 ..0), (세로 11, 11 ... 0) 했지만

뿌요판을 정 반대로 뒤집고 시작하면 끝이 아니라 앞 (가로 0.. 6) (세로 0..11)로 변형하여 더 쉽게 풀이할 수 있다.

 

@Test
internal fun testArrayReverse(){
    val arr = arrayOf(
        charArrayOf('.', 'Y', 'G', '.', '.', '.'),
        charArrayOf('R', 'R', 'Y', 'G', '.', '.'),
        charArrayOf('R', 'R', 'Y', 'G', 'G', '.')
    )
    arr.reverse()

    for (row in arr) {
        println(row)
    }
}

뒤집힌 상태로 풀이하면 0,0부터 조사할 수 있어 더 간단하다.