[백준 12100번] 2048 (Easy) - Kotlin

12100번 2048 (Easy) - Kotlin

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

12100번: 2048 (Easy)

---

조건

• 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것
• 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 됨
• 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없음

---

입력

• N → 첫째 줄에 보드의 크기, N in 1 .. 20
• 둘째 줄부터 N개의 줄에는 게임판의 초기 상태
• 0은 빈 칸 이외는 모두 블록을 나타냄
• 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴

---

출력

• 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력

---

테스트 케이스

/* 
3
2 2 2
4 4 4
8 8 8

Output
16

5
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 4 0 2 2

Output
32

5
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 2 0 2 2
2 2 0 4 2 

Output
32

*/

---

첫 번째 풀이 - 틀렸습니다

import kotlin.math.max

private class Solution12100 {
    private val directions = arrayOf(
        Direction.DOWN,
        Direction.LEFT,
        Direction.UP,
        Direction.RIGHT
    )

    private var max = 0

    fun solution(
        n: Int,
        map: Array<IntArray>
    ): Int {
        max = 0

        dfs(0, map)

        return max
    }

    private fun dfs(depth: Int, map: Array<IntArray>) {
        if (depth == 5) {
            return
        }

        for (direction in directions) {
            val copyMap = Array(map.size) { row -> IntArray(map.size) { col -> map[row][col] } }
            copyMap.move(direction)

            dfs(depth + 1, copyMap)
        }
    }

    private fun Array<IntArray>.move(direction: Direction) {
        when (direction) {
            Direction.RIGHT -> for (row in this) {
                for (i in row.size - 2 downTo 0) {
                    val item = row[i]
                    val next = row.getOrNull(i + 1) ?: continue

                    when (next) {
                        0 -> {
                            // 빈칸
                            row[i + 1] = item
                            row[i] = 0

                            if (row[i + 1] > max) {
                                max = row[i + 1]
                            }
                        }
                        item -> {
                            // 다음 칸이 현재와 동일할 때
                            row[i + 1] = row[i + 1] * 2
                            row[i] = 0
                        }
                        else -> Unit
                    }

                    max = max(row[i + 1], max)
                    max = max(row[i], max)
                }
            }
            Direction.LEFT -> for (row in this) {
                for (i in row.indices) {
                    val item = row[i]
                    val prev = row.getOrNull(i - 1) ?: continue

                    when (prev) {
                        0 -> {
                            // 빈칸
                            row[i - 1] = item
                            row[i] = 0
                        }
                        item -> {
                            // 다음 칸이 현재와 동일할 때
                            row[i - 1] = row[i - 1] * 2
                            row[i] = 0
                        }
                        else -> Unit
                    }

                    max = max(row[i - 1], max)
                    max = max(row[i], max)
                }
            }
            Direction.DOWN -> for (n in this.indices) {
                for (i in this.size - 2  downTo 0) {
                    val item = this[i][n]
                    val next = this.getOrNull(i + 1)?.get(n) ?: continue
                    when (next) {
                        0 -> {
                            // 빈칸
                            this[i + 1][n] = item
                            this[i][n] = 0
                        }
                        item -> {
                            // 다음 칸이 현재와 동일할 때
                            this[i + 1][n] = this[i + 1][n] * 2
                            this[i][n] = 0
                        }
                        else -> Unit
                    }

                    max = max(this[i + 1][n] , max)
                    max = max(this[i][n] , max)
                }
            }
            Direction.UP -> for (n in this.indices) {
                for (i in indices) {
                    val item = this[i][n]
                    val prev = this.getOrNull(i - 1)?.get(n) ?: continue
                    when (prev) {
                        0 -> {
                            // 빈칸
                            this[i - 1][n] = item
                            this[i][n] = 0
                        }
                        item -> {
                            // 다음 칸이 현재와 동일할 때
                            this[i - 1][n] = this[i - 1][n] * 2
                            this[i][n] = 0
                        }
                        else -> Unit
                    }

                    max = max(this[i - 1][n] , max)
                    max = max(this[i][n] , max)
                }
            }
        }
    }

     enum class Direction {
        RIGHT,
        LEFT,
        UP,
        DOWN,
    }
}

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

    val n = br.readLine().toInt()
    val map = Array(n) { _ ->
        val str = br.readLine().split(" ").map { it.toInt() }
        IntArray(n) { str[it] }
    }

    bw.append("${Solution12100().solution(n, map)}\\n")
    bw.flush()

    br.close()
    bw.close()
}

• 처음 주어진 Input 예시로만 체크를 해서 이동 방향으로 모든 블록을 밀어버리는 것이 아닌 한칸만 이동하는 것으로 잘못 구현하여 실패

---

두 번째 풀이 - 맞았습니다

import kotlin.math.max

private class Solution12100 {
    private val directions = arrayOf(
        Direction.DOWN,
        Direction.LEFT,
        Direction.UP,
        Direction.RIGHT
    )

    private var max = 0

    fun solution(
        n: Int,
        map: Array<IntArray>
    ): Int {
        max = 0

        dfs(0, map)

        return max
    }

    private fun dfs(depth: Int, map: Array<IntArray>) {
        if (depth == 5) {
            return
        }

        for (direction in directions) {
            val copyMap = Array(map.size) { row -> IntArray(map.size) { col -> map[row][col] } }
            copyMap.move(direction)
            dfs(depth + 1, copyMap)
        }
    }

    private fun Array<IntArray>.move(direction: Direction) {
        val deque = ArrayDeque<Int>()

        when (direction) {
            Direction.RIGHT -> for (row in this.indices) {
                for (col in this.indices) {
                    when (val item = this[row][col]) {
                        0 -> Unit
                        else -> {
                            deque.add(item)
                            this[row][col] = 0
                        }
                    }
                }

                var newCol = this.size - 1

                while (deque.isNotEmpty()) {
                    val last = deque.removeLast()

                    this[row][newCol] = if (deque.isNotEmpty() && deque.last() == last) {
                        last + deque.removeLast()
                    } else {
                        last
                    }

                    max = max(this[row][newCol], max)
                    newCol -= 1
                }
            }
            Direction.LEFT -> for (row in this.indices) {
                for (col in this.indices) {
                    when (val item = this[row][col]) {
                        0 -> Unit
                        else -> {
                            deque.add(item)
                            this[row][col] = 0
                        }
                    }
                }

                var newCol = 0

                while (deque.isNotEmpty()) {
                    val first = deque.removeFirst()

                    this[row][newCol] = if (deque.isNotEmpty() && deque.first() == first) {
                        first + deque.removeFirst()
                    } else {
                        first
                    }

                    max = max(this[row][newCol], max)
                    newCol += 1
                }
            }
            Direction.DOWN -> for (col in this.indices) {
                for (row in this.indices) {
                    when (val item = this[row][col]) {
                        0 -> Unit
                        else -> {
                            deque.add(item)
                            this[row][col] = 0
                        }
                    }
                }

                var newRow = this.size - 1

                while (deque.isNotEmpty()) {
                    val last = deque.removeLast()

                    this[newRow][col] = if (deque.isNotEmpty() && deque.last() == last) {
                        last + deque.removeLast()
                    } else {
                        last
                    }

                    max = max(this[newRow][col], max)
                    newRow -= 1
                }
            }
            Direction.UP -> for (col in this.indices) {
                for (row in this.indices) {
                    when (val item = this[row][col]) {
                        0 -> Unit
                        else -> {
                            deque.add(item)
                            this[row][col] = 0
                        }
                    }
                }

                var newRow = 0

                while (deque.isNotEmpty()) {
                    val first = deque.removeFirst()

                    this[newRow][col] = if (deque.isNotEmpty() && deque.first() == first) {
                        first + deque.removeFirst()
                    } else {
                        first
                    }

                    max = max(this[newRow][col], max)
                    newRow += 1
                }
            }
        }
    }

     enum class Direction {
        RIGHT,
        LEFT,
        UP,
        DOWN,
    }
}

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

    val n = br.readLine().toInt()
    val map = Array(n) { _ ->
        val str = br.readLine().split(" ").map { it.toInt() }
        IntArray(n) { str[it] }
    }

    bw.append("${Solution12100().solution(n, map)}\\n")
    bw.flush()

    br.close()
    bw.close()
}

• ArrayDeque를 이용하여 블록을 저장하고 해당 블록을 기준으로 새로 값 저장