19235 모노미도미노

문제 링크

배운 점

• ||연산은 앞 부분의 계산이 TRUE가 나오면 뒷 부분 연산을 시행하지 않는다점을 체험하였다.
• 변수를 명명할 때 헷갈리지 않도록 주의
• kotlin은 제한시간 1초를 초과한다. 새로운 IR backend를 사용하면 통과할 것으로 예상된다.

Kotlin

package baekjoon.kotlin.p19235

private fun readNum() = readLine()!!.toInt()
private fun readNums() = readLine()!!.split(" ").map { it.toInt() }

private val gBoard = Array(6) { Array(4) { 0 } }
private val bBoard = Array(6) { Array(4) { 0 } }
private val gBlock = listOf(listOf(0 to 0), listOf(0 to 0, 0 to 1), listOf(0 to 0, 1 to 0))
private val bBlock = listOf(listOf(0 to 0), listOf(0 to 0, 1 to 0), listOf(0 to 0, 0 to 1))

private val d = arrayOf(-1 to 0, 0 to -1, 0 to 1)

fun main() {
    val N = readNum()
    var blockNum = 1

    fun moveIfFloat(): Boolean {
        // 떠 있는 블록을 바닥에 붙인다. 블록을 움직였으면 true를 반환
        fun dropTheBlock(board: Array<Array<Int>>): Boolean {
            var ret = false
            for (r in 4 downTo 0) for (c in 3 downTo 0) {
                if (board[r][c] == 0) continue
                if (board[r + 1][c] != 0) continue

                val blocks = mutableListOf(r to c)
                val curBlock = board[r][c]
                d.forEach {
                    if (r + it.first >= 0 && c + it.second >= 0 && c + it.second < 4 && curBlock == board[r + it.first][c + it.second])
                        blocks.add(r + it.first to c + it.second)
                }
                var isMovable = true
                while (isMovable) {
                    for (i in blocks.indices) {
                        if (blocks[i].first == 5) {
                            isMovable = false
                            break
                        }
                        val n = board[blocks[i].first + 1][blocks[i].second]
                        if (n == 0 || n == curBlock) {
                            blocks[i] = blocks[i].first + 1 to blocks[i].second
                        } else {
                            isMovable = false
                            break
                        }
                    }
                    if (isMovable) {
                        ret = true
                        blocks.forEach {
                            board[it.first - 1][it.second] = 0
                            board[it.first][it.second] = curBlock
                        }
                    }
                }
            }

            return ret
        }
        val g = dropTheBlock(gBoard)
        val b = dropTheBlock(bBoard)

        return g || b
    }

    fun cleanUpLines(): Int {
        // 파란 보드와 초록 보드의 라인을 이룬 부분을 제거한다. 제거 했으면 true를 반환
        fun removeLine(board: Array<Array<Int>>): Int {
            var ret = 0
            for (r in 2 until 6) {
                if (!board[r].contains(0)) {
                    for (c in 0 until 4) board[r][c] = 0
                    ret++
                }
            }
            return ret
        }

        var ret = 0
        do {
            ret += removeLine(gBoard) + removeLine(bBoard)
        } while (moveIfFloat())

        return ret
    }

    fun moveIfOverflow(): Boolean {
        // 쌓인 블록이 넘치면 가장 바닥 부분을 한 줄 제거한다. 제거했으면 true를 반환
        fun moveBoard(board: Array<Array<Int>>): Boolean {
            if (board[0].any { it != 0 }) {
                for (c in 0 until 4) {
                    board[4][c] = 0
                    board[5][c] = 0
                }
                return true
            } else if (board[1].any { it != 0 }) {
                for (c in 0 until 4) board[5][c] = 0
                return true
            }
            return false
        }
        val g = moveBoard(gBoard)
        val b = moveBoard(bBoard)
        return  g || b
    }

    fun pileBlock(t: Int, x: Int, y: Int) {
        // 블록을 쌓는다.
        gBlock[t - 1].forEach { gBoard[it.first][y + it.second] = blockNum }
        bBlock[t - 1].forEach { bBoard[it.first][x + it.second] = blockNum }
        moveIfFloat()
    }

    var ret = 0

    repeat(N) {
        val (t, x, y) = readNums()

        pileBlock(t, x, y)
        ret += cleanUpLines()
        if (moveIfOverflow())
            moveIfFloat()
        blockNum++
    }

    println(ret)
    println(gBoard.sumBy { r -> r.sumOf { (if (it == 0) 0 else 1).toInt() } } +
            bBoard.sumBy { r -> r.sumOf { (if (it == 0) 0 else 1).toInt() } })

    println()
    gBoard.forEach { r ->
        r.forEach {
            print("$it ")
        }
        println()
    }
    println()
    bBoard.forEach { r ->
        r.forEach {
            print("$it ")
        }
        println()
    }
}

Java

package baekjoon.java.p19235;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int N;
    private static int blockNum;
    private static int[][] gBoard = new int[6][4];
    private static int[][] bBoard = new int[6][4];
    private static int[][] d = {{-1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        int ret = 0;
        while (N-- != 0) {
            blockNum++;
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int t, x, y;
            t = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            pileBlock(t, x, y);
            ret += cleanUpLines();
            if (moveIfOverflow())
                moveIfFloat();
        }
        bw.write(Integer.toString(ret));
        int cnt = 0;
        for(int r = 0; r < 6; r++) for(int c = 0; c < 4; c++) {
            if(gBoard[r][c] != 0) cnt++;
            if(bBoard[r][c] != 0) cnt++;
        }
        bw.newLine();
        bw.write(Integer.toString(cnt));
        bw.newLine();
        bw.flush();

        /*for(int[] r : gBoard) {
            for (int v : r) {
                System.out.print(Integer.toString(v) + " ");
            }
            System.out.println();
        }
        System.out.println();
        for(int[] r : bBoard) {
            for (int v : r) {
                System.out.print(Integer.toString(v) + " ");
            }
            System.out.println();
        }*/
    }

    private static boolean moveIfFloat() {
        boolean g = dropTheBlock(gBoard);
        boolean b = dropTheBlock(bBoard);
        return g || b;
    }

    public static boolean isInside(int r, int c) {
        return r < 6 && r >= 0 && c < 4 && c >= 0;
    }

    private static boolean dropTheBlock(int[][] board) {
        boolean ret = false;
        for (int r = 4; r >= 0; r--) {
            for (int c = 3; c >= 0; c--) {
                if (board[r][c] == 0) continue;
                if (board[r + 1][c] != 0) continue;

                ArrayList<Pair> blocks = new ArrayList<>();
                int boardNum = board[r][c];
                blocks.add(new Pair(r, c));
                for (int[] mv : d) {
                    int nr = r + mv[0], nc = c + mv[1];
                    if (isInside(nr, nc) && board[nr][nc] == boardNum)
                        blocks.add(new Pair(nr, nc));
                }
                int dist = 99;
                for (Pair block : blocks) {
                    int cnt = 0;
                    for (int i = block.f + 1; i < 6; i++) {
                        if (board[i][block.s] != 0 && (board[i][block.s] != boardNum))
                            break;
                        cnt++;
                    }
                    dist = Integer.min(dist, cnt);
                }
                if (dist != 0) {
                    ret = true;
                }
                for (Pair block : blocks) {
                    board[block.f][block.s] = 0;
                }
                for(Pair block : blocks) {
                    board[block.f + dist][block.s] = boardNum;
                }
            }
        }
        return ret;
    }

    private static boolean moveIfOverflow() {
        int gMv = getOverflowed(gBoard);
        int bMv = getOverflowed(bBoard);

        for (int r = 6 - gMv; r < 6; r++)
            for (int c = 0; c < 4; c++)
                gBoard[r][c] = 0;
        for (int r = 6 - bMv; r < 6; r++)
            for (int c = 0; c < 4; c++)
                bBoard[r][c] = 0;

        return gMv != 0 || bMv != 0;
    }

    private static int getOverflowed(int[][] board) {
        for (int r = 0; r < 2; r++) {
            for (int c = 0; c < 4; c++) {
                if (board[r][c] != 0) {
                    return 2 - r;
                }
            }
        }
        return 0;
    }

    private static int cleanUpLines() {
        int ret = 0;

        do {
            for (int r = 2; r < 6; r++) {
                int gCnt = 0, bCnt = 0;
                for (int c = 0; c < 4; c++) {
                    if (gBoard[r][c] != 0) gCnt++;
                    if (bBoard[r][c] != 0) bCnt++;
                }
                if (gCnt == 4) {
                    ret++;
                    for (int c = 0; c < 4; c++) gBoard[r][c] = 0;
                }
                if (bCnt == 4) {
                    ret++;
                    for (int c = 0; c < 4; c++) bBoard[r][c] = 0;
                }
            }
        } while (moveIfFloat());

        return ret;
    }

    private static void pileBlock(int t, int x, int y) {
        switch (t) {
            case 2:
                gBoard[0][y + 1] = blockNum;
                bBoard[1][x] = blockNum;
                break;
            case 3:
                gBoard[1][y] = blockNum;
                bBoard[0][x + 1] = blockNum;
                break;
        }
        gBoard[0][y] = blockNum;
        bBoard[0][x] = blockNum;
    }

    private static class Pair {
        public int f;
        public int s;

        public Pair(int f, int s) {
            this.f = f;
            this.s = s;
        }
    }
}