[백준] #12100: 2048 (Easy)

1. Problem Link

• https://www.acmicpc.net/problem/12100

2. Source Code

• moveBoard(direction) 함수에 대한 이해를 돕기 위한 블로그 (https://jellyinghead.tistory.com/53)

var n = 0
var answer = 0
lateinit var board: Array<MutableList<Int>>

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    n = br.readLine().toInt()
    board = Array(n) { mutableListOf() }
    repeat(n) {
        board[it] = br.readLine().split(" ").map { it.toInt() }.toMutableList()
    }
    startGame(0)
    bw.write("$answer")

    br.close()
    bw.close()
}

fun startGame(cnt: Int) {
    if (cnt == 5) {
        for (i in 0 until n) {
            answer = maxOf(answer, board[i].maxOf { it })
        }
        return
    }

    // store original board
    val tempBoard = Array(n) { mutableListOf<Int>() }
    board.forEachIndexed { index, mutableList ->
        tempBoard[index].addAll(mutableList)
    }

    for (i in 0 until 4) {
        moveBoard(i)
        startGame(cnt + 1)
        // reset
        tempBoard.forEachIndexed { index, mutableList ->
            board[index].clear()
            board[index].addAll(mutableList)
        }
    }
}

fun moveBoard(direction: Int) {
    when (direction) {
        0 -> {
            // 위
            for (col in 0 until n) {
                var index = 0
                var temp = 0
                for (row in 0 until n) {
                    if (board[row][col] == 0) continue
                    if (board[row][col] == temp) {
                        board[index - 1][col] = temp * 2
                        board[row][col] = 0
                        temp = 0
                    } else {
                        temp = board[row][col]
                        board[row][col] = 0
                        board[index++][col] = temp
                    }
                }
            }
        }
        1 -> {
            // 아래
            for (col in 0 until n) {
                var index = n - 1
                var temp = 0
                for (row in n - 1 downTo 0) {
                    if (board[row][col] == 0) continue
                    if (board[row][col] == temp) {
                        board[index + 1][col] = temp * 2
                        board[row][col] = 0
                        temp = 0
                    } else {
                        temp = board[row][col]
                        board[row][col] = 0
                        board[index--][col] = temp
                    }
                }
            }
        }
        2 -> {
            // 왼쪽
            for (row in 0 until n) {
                var index = 0
                var temp = 0
                for (col in 0 until n) {
                    if (board[row][col] == 0) continue
                    if (board[row][col] == temp) {
                        board[row][index - 1] = temp * 2
                        board[row][col] = 0
                        temp = 0
                    } else {
                        temp = board[row][col]
                        board[row][col] = 0
                        board[row][index++] = temp
                    }
                }
            }
        }
        3 -> {
            // 오른쪽
            for (row in 0 until n) {
                var index = n - 1
                var temp = 0
                for (col in n - 1 downTo 0) {
                    if (board[row][col] == 0) continue
                    if (board[row][col] == temp) {
                        board[row][index + 1] = temp * 2
                        board[row][col] = 0
                        temp = 0
                    } else {
                        temp = board[row][col]
                        board[row][col] = 0
                        board[row][index--] = temp
                    }
                }
            }
        }
        else -> {}
    }
}

3. Complexity

• Time : O(N^2)
• Space : O(N^2)