[コートリン]白準12100号:2048-三星ソフトウェア能力試験出題

問題に答えろ!

に答える

この問題の時間は5秒に制限されていますが、4方向に5回移動するだけなので、フルナビゲーション(逆トレース)が使用されます.

ついせき

上下左右に5回移動する角度から最高値を求めればよい.

fun permutation(cnt: Int) {
    if (cnt == 5) {
        board.forEach { array ->
            array.forEach { num ->
                answer = max(answer, num)
            }
        }
        return
    }

    val clone_board = Array(n) {IntArray(n)}
    for (i in board.indices) {
        clone_board[i] = board[i].clone()
    }
    for (i in 0..3) {
        move(i)
        permutation(cnt + 1)
        for (i in board.indices) {
            board[i] = clone_board[i].clone()
        }
    }
}

ブロックの移動

Blockを移動する際に指摘すべき部分があります
1回の移動では、マージされたブロックは別のブロックと再マージできません.
たとえば、次のゲーム版が存在するとします.
|2|2|2|
|2|2|2|
|4|4|4|
ここで1回上に移動すると、結果値は次のようになります.
|4|4|4|
|4|4|4|
|0|0|0|
したがって、스택とcursorという変数を使用して、ブロックが重複して結合できないことを保証するために方向に論理を記述します.

fun move(rotate: Int) {
    val clone_board = Array(n) { IntArray(n) }
    when (rotate) {
        0 -> {
            // 위 쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[i][c] = list[i]
                }
            }
        }
        1 -> {
            // 아래쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }

                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[board.size - 1 - i][c] = list[i]
                }
            }
        }
        2 -> {
            // 왼쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][i] = list[i]
                }
            }
        }
        3 -> {
            // 오른쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][board.size - 1 - i] = list[i]
                }
            }
        }
    }
    for (i in board.indices) {
        board[i] = clone_board[i].clone()
    }
}

Source Code

package 삼성SW역량테스트.`12100번_2048`

import java.util.*
import kotlin.math.max

lateinit var board: Array<IntArray>
var n: Int = 0
var answer = 0
fun main() {
    n = readln().toInt()
    board = Array(n) { IntArray(n) }

    for (i in board.indices) {
        val str = readln()
        board[i] = str.split(" ").map { it.toInt() }.toIntArray()
    }

    permutation(0)
    println(answer)

}
fun permutation(cnt: Int) {
    if (cnt == 5) {
        board.forEach { array ->
            array.forEach { num ->
                answer = max(answer, num)
            }
        }
        return
    }

    val clone_board = Array(n) {IntArray(n)}
    for (i in board.indices) {
        clone_board[i] = board[i].clone()
    }
    for (i in 0..3) {
        move(i)
        permutation(cnt + 1)
        for (i in board.indices) {
            board[i] = clone_board[i].clone()
        }
    }
}

fun move(rotate: Int) {
    val clone_board = Array(n) { IntArray(n) }
    when (rotate) {
        0 -> {
            // 위 쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[i][c] = list[i]
                }
            }
        }
        1 -> {
            // 아래쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }

                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[board.size - 1 - i][c] = list[i]
                }
            }
        }
        2 -> {
            // 왼쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][i] = list[i]
                }
            }
        }
        3 -> {
            // 오른쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][board.size - 1 - i] = list[i]
                }
            }
        }
    }
    for (i in board.indices) {
        board[i] = clone_board[i].clone()
    }
}