[백준 20061] - 모노미노도미노 2(Kotlin)[골드2]

문제

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

20061번: 모노미노도미노 2

문제 풀이

우선 내용이 굉장히 길고 문제를 이해하는데 너무 오래 걸렸던 문제이다.

만약 본인의 코드가 틀렸거나 막혔다면 내 해석이 도움이 되었으면 좋겠다.

 

우선 보드는 빨간색, 파란색, 초록색 3가지의 보드가 있다.

하나의 배열로 관리하는것이 아닌 3가지의 보드라는 클래스를 생성해서 관리하도록 했다.

 

data class Block(val id: String) {
		lateinit var graph: Array<BooleanArray>
        var score = 0
}

Block이라는 클래스는 생성자로 색깔을 스트링 값으로 가지고, Boolean을 인자로 하는 2차원 배열과 score를 가진다.

 

Block에는 여러 함수가 있다.

setSize : 색깔에 맞게 2차원 배열의 크기를 설정해 준다. 파란색 -> 4*6, 초록색 -> 6*4

putBlock : 2차원 보드에 블록을 놓는 함수

checkCol : 파란색에 해당하는 기능, 행이 가득찼다면 점수를 1점 증가시킴.

clearCol : 해당 행을 비워주는 함수.

pushCol : 해당 행을 기준으로 왼쪽에 있는 행들을 오른쪽으로 한 칸씩 밀어줌.

checkRow : 초록색에 해당하는 기능. 열이 가득 찼다면 점수를 1점 증가시킴.

clearRow : 해당 열을 비워주는 함수

pushRow: 해당 열을 기준으로 위쪽에 있는 열을 아래쪽으로 한칸씩 밀어줌.

moveBlock : 파란색과 초록색의 연한블록에 위치한 행과 열의 개수만큼 오른쪽으로 밀어줌.

getBlock : 보드의 블록 갯수를 반환함.

 

알고리즘의 순서는 이러하다.

1. 입력받은 블록의 종류,x,y를 배열에 저장함.
2. 배열의 원소(블록,x,y)를 파란색, 초록색에 각각 putBlock
3. 파란색, 초록색 열과 행을 검사
4. 파란색, 초록색의 연한 블록을 검사해서 밀어줌.
5. 점수와 블록 반환

여기서 내가 가장 헷갈렸던 부분은 함수의 실행순서이다.

기존에는 보드에 블록을 넣고, 연한블록을 검사해서 밀어주고, 열과 행을 검사했다.

하지만 계속 특정 케이스에서 틀려서 문제를 읽고 열과 행을 검사하고, 연한 블록을 검사해서 밀어주는 순서로 실행을 하니 통과했다.

실제로 순서를 바꿔도 문제에서 주어진 테스트케이스는 통과할 수 있다는 점이 가장 무서운 사실이다..

 

각 함수에 대해서 설명하면,

색깔 보드에 블록을 놓는 함수는 색깔과 블록의 종류에 따라서 달라진다.

우선 블록의 이동 조건은 경계를 만나거나, 다른 블록을 만날 경우 이동을 중지한다.

 

1*1의 블록 

• 파란색 :  x를 고정시키고 y를 변화시키면서 배열 끝까지 이동시키면서 다른 블록을 만나기 전까지 검사해 준다.
• 초록색:  y를 고정시키고 x를 변화시키면서 배열 끝까지 이동시키면서 다른 블록을 만나기 전까지 검사해 준다.

1*2의 블록

• 파란색:  x를 고정시키고 , y와 y-1을 배열 끝까지 이동시키면서 다른 블록을 만나기 전까지 검사해 준다.
• 초록색 : x를 고정시키고 를 변화시키면서 x와 x+1 배열 끝까지 이동시키면서 다른 블록을 만나기 전까지 검사해 준다.

굳이 y와 y-1 , x와 x+1은 정해져 있지 않고, 해당 좌표를 기준으로 2칸을 검사해 주면 된다.

 

2*1의 블록

• 파란색 : x를 기준으로 2칸 검사하고, y를 배열 끝까지 이동시키면서 다른 블록을 만나기 전까지 검사해 준다.
• 초록색 : x를 기준으로 2칸 검사하고, x를 배열 끝까지 이동시키면서 다른 블록을 만나기 전까지 검사해 준다.

각 블록을 검사하면서 가장 멀리 가는 구간까지의 값을 기록해서 해당 값을 이용해서 graph에 블록을 채워준다.

 

이렇게 블록을 채우면 파란색은 행을 검사하고, 초록색은 열을 검사해야 한다. (checkRow, checkCol)

행과 열을 검사해서 꽉 차있다면 해당 행과 열을 비워줘야 한다. (clearRow , clearCol)

비워줌과 동시에 해당 행 or 열을 기준으로 밀어줘야 한다. (pushRow, pushCol)

밀어주는 건 해당 행 or 열을 기준으로 왼쪽 값 or 위쪽 값을 당겨오면 된다.

블록을 놓고, 열과 행을 검사했다면, 이제 연한 블록 쪽에 값이 있는지 판단하고 (moveBlock),

차지한 개수만큼 밀어줘야 한다. (pushRow, pushCol)

 

작업이 모두 끝나고, score는 block 변수에 있는 score를 더해주고, 남아있는 블록의 개수는 getBlock을 통해서 처리한다.

 

우선 알고리즘의 흐름과 설명은 이러합니다.

해당 문제에서 핵심은 블록의 종류와 색깔에 따라 이동시키는 것이 핵심이라고 생각합니다.

적절하게 블록을 배치하면 그 뒤로는 조금만 고민을 하면 되는 것이라서,

설명을 상세하게 하진 않았고, 코드를 통해서 확인하시면 될 거 같습니다.

 

전체 코드

package Implementation.`20061_모노미노도미노2`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader

class `20061` {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private lateinit var blue: Block
    private lateinit var green: Block
    var testcase = mutableListOf<Triple<Int, Int, Int>>()

    init {
        makeBlock()
        input()
    }

    fun input() {
        val input = br.readLine()
        n=input.toInt()
        for (i in 0 until n) {
            val line = br.readLine().split(" ")
            testcase.add(Triple(line[0].toInt(), line[1].toInt(), line[2].toInt()))
        }
        for (case in testcase) {
            putBlock(case.first, case.second, case.third)
        }
        println(getScore())
        print(getBlock())

    }

    fun getScore(): Int { //점수 반환
        return blue.score + green.score
    }

    fun getBlock(): Int { //블록 반환
        return blue.getBlock() + green.getBlock()
    }

    private fun putBlock(option: Int, x: Int, y: Int) { //처음에 블록 놓기, 빨간색에 놓이는 블록은 겹치는 일이 없을 거임
        blue.putBlock(x, y, option) //파란색 옮기고 파란색은 맨 끝 행부터 시작
        blue.score+=blue.checkCol()
        blue.moveBlock(x, y)
        green.putBlock(x, y, option)
        green.score+=green.checkRow()
        green.moveBlock(x, y)
    }

    private fun makeBlock() { //블록 만들기
        blue = Block("B")
        green = Block("G")
    }
    data class Block(val id: String) {
        lateinit var graph: Array<BooleanArray>
        var score = 0

        init {
            setSize()
        }

        private fun setSize() { //색깔 별로 블록의 배열을 정함. R : 4x4, B : 4x6, G : 6x4
            when (id) {
                "B" -> graph = Array(4) { BooleanArray(6) { false} }
                "G" -> graph = Array(6) { BooleanArray(4) { false} }
            }
        }


        fun moveBlock(x: Int, y: Int) { //블록에 크기만큼 위치에 넣기.
            var cnt = 0
            when (id) {
                "B" -> { //y가 0~1
                    for (col in 0..1) {
                        for (row in 0 until graph.size) {
                            if (graph[row][col]) { //true면 0~1에 있는거임.
                                cnt++
                                break
                            }
                        }
                    }
                    for (i in 0 until cnt) {
                        pushCol(graph[0].size-1)
                    }
                }

                "G" -> { //x가 0~1
                    for (row in 0..1) {
                        for (col in 0 until graph[row].size) {
                            if (graph[row][col] ) { //하나라도 잇을경우 -->
                                cnt++
                                break
                            }
                        }
                    }
                    for (i in 0 until cnt) {
                        pushRow(graph.size-1)
                    }
                }
            }
        }

        fun putBlock(x: Int, y: Int, opt: Int) {
            when (id) {
                "B" ->
                    when (opt) {
                        1 -> {
                            var max = 0
                            for (col in 0 until graph[0].size) {
                                if (!graph[x][col]) {
                                    max = col
                                } else break
                            }
                            graph[x][max] = true
                        }

                        2 -> {
                            var max = 0
                            for (col in 1 until graph[0].size) {
                                if (!graph[x][col - 1] && !graph[x][col]) {
                                    max = col
                                } else break
                            }
                            graph[x][max] = true
                            graph[x][max - 1] = true
                        }

                        3 -> {
                            var max = 0
                            for (col in 0 until graph[0].size) {
                                if (!graph[x][col] && !graph[x + 1][col]) {
                                    max = col
                                } else break
                            }
                            graph[x][max] = true
                            graph[x + 1][max] = true
                        }
                    }

                "G" -> {
                    when (opt) {
                        1 -> {
                            var max = 0
                            for (row in 0 until graph.size) {
                                if (!graph[row][y]) {
                                    max = row
                                } else break
                            }
                            graph[max][y] = true
                        }

                        2 -> {
                            var max = 0
                            for (row in 0 until graph.size) {
                                if (!graph[row][y] && !graph[row][y + 1]) {
                                    max = row
                                } else break
                            }
                            graph[max][y] = true
                            graph[max][y + 1] = true
                        }

                        3 -> {
                            var max = 0
                            for (row in 1 until graph.size) {
                                if (!graph[row][y] && !graph[row - 1][y]) {
                                    max = row
                                } else break
                            }
                            graph[max - 1][y] = true
                            graph[max][y] = true
                        }
                    }
                }
            }
        }
        fun checkRow(): Int { //열마다 한줄이 차있는지 확인
            var cnt = 0
            for (row in 0 until graph.size) {
                if (!graph[row].contains(false)) {
                    cnt++
                    clearRow(row)
                }
            }
            return cnt
        }

        fun checkCol(): Int { //행마다 한줄이 차있는지 확인
            var flag = false
            var cnt = 0
            for (col in 0 until graph[0].size) {
                flag = true
                for (row in 0 until graph.size) {
                    if (!graph[row][col]) {
                        flag = false
                        break
                    }
                }
                if (flag) {
                    cnt++
                    clearCol(col)
                }
            }
            return cnt
        }

        fun clearCol(col: Int) { //해당 행을 비운다.
            for (row in 0 until graph.size) {
                graph[row][col] = false
            }
            pushCol(col) //해당 행을 기준으로 왼쪽에 있는 블록들을 오른쪽으로 밀어준다.

        }

        fun clearRow(row: Int) { //해당 열을 비운다.
            for (col in 0 until graph[row].size) {
                graph[row][col] = false
            }
            pushRow(row) //열을 기준으로 위쪽에 있는 블록들을 아래로 밀어준다.
        }

        fun pushRow(row: Int) { // 위에있는 블록을아래로 밀기
            for (r in row downTo 1) {
                for (col in 0 until graph[r].size) {
                    graph[r][col] = graph[r - 1][col]
                }
            }
            for(c in 0 until graph[0].size){
                graph[0][c]=false
            }
        }

        fun pushCol(col: Int) { // 사라진 왼쪽에 있는 블록 오른쪽으로 밀기
            for (c in col  downTo 1) {
                for (row in 0 until graph.size) {
                    graph[row][c] = graph[row][c - 1]
                }
            }
            for(row in 0 until graph.size){
                graph[row][0]=false
            }
        }

        fun getBlock(): Int { //잔여 블록확인
            var block = 0
            for (row in graph) {
                for (col in row) {
                    if (col)
                        block++
                }
            }
            return block
        }
    }
}

fun main() {

    val solution = `20061`()

}