[백준] 12100 2048 (Easy)

 

 

🔒 문제

 

 

🧠 아이디어

접근 방법

ArrayDeque 를 사용하여 테트리스의 밀어 붙이기 아이디어를 사용.

이 때, index 방향을 제대로 설정해줘야한다.

 

합치는 구간에서도 진행 방향쪽 블록을 먼저 합쳐야 하기 때문에 index 진행 방향에 유의해야한다.

이 부분에서 실수하기 굉장히 쉬운 문제다.

 

 

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

enum class Direction{
    EAST,
    WEST,
    SOUTH,
    NORTH
}

// (1) 0으로 빈칸은 모두 당겨오기 처리
// (2) 당겨온 다음에 겹치기.
// 겹칠 때 상태 확인
// Current modification 방지

private fun moveRight(map: Array<ArrayDeque<Int>>) {
    // 오른쪽으로 다 붙이기
    for (deque in map) {
        for (idx in deque.indices) {
            if (deque[idx] == 0) {
                deque.removeAt(idx)
                deque.addFirst(0)
            }
        }
    }
    // 붙였으면 겹치기
    for (deque in map) {
        for (idx in deque.lastIndex downTo 1) {
            if (deque[idx] == 0) break
            if (deque[idx] != deque[idx - 1]) continue
            deque[idx] *= 2
            deque.removeAt(idx - 1)
            deque.addFirst(0)
        }
    }
}

private fun moveLeft(map: Array<ArrayDeque<Int>>) {
    // 왼쪽으로 다 붙이기
    for (deque in map) {
        for (idx in deque.indices.reversed()) {
            if (deque[idx] == 0) {
                deque.removeAt(idx)
                deque.addLast(0)
            }
        }
    }
    // 붙였으면 겹치기
    for (deque in map) {
        for (idx in 0 until deque.size - 1) {
            if (deque[idx] == 0) break
            if (deque[idx] != deque[idx + 1]) continue
            deque[idx] *= 2
            deque.removeAt(idx + 1)
            deque.addLast(0)
        }
    }

}

private fun moveDown(map: Array<ArrayDeque<Int>>) {
    val deque = Array(map.size){ArrayDeque<Int>(map.size)}

    for (col in map[0].indices) {
        for (row in map.indices) {
            deque[col].addLast(map[row][col])
        }
    }

    // 남쪽으로 다 붙이기
    for (colQueue in deque) {
        for (rowIdx in colQueue.indices) {
            if (colQueue[rowIdx] == 0) {
                colQueue.removeAt(rowIdx)
                colQueue.addFirst(0)
            }
        }
    }

    // 붙였으면 겹치기
    for (colQueue in deque) {
        for (idx in colQueue.lastIndex downTo 1) {
            if (colQueue[idx] == 0) break
            if (colQueue[idx] != colQueue[idx - 1]) continue
            colQueue[idx] *= 2
            colQueue.removeAt(idx - 1)
            colQueue.addFirst(0)
        }
    }

    // 덮어쓰기
    for (col in deque.indices) {
        for (row in deque[col].indices) {
            map[row][col] = deque[col][row]
        }
    }
}

private fun moveUp(map: Array<ArrayDeque<Int>>) {
    val deque = Array(map.size){ArrayDeque<Int>(map.size)}

    for (col in map[0].indices) {
        for (row in map.indices) {
            deque[col].addLast(map[row][col])
        }
    }

    // 북쪽으로 다 붙이기
    for (colQueue in deque) {
        for (rowIdx in colQueue.indices.reversed()) {
            if (colQueue[rowIdx] == 0) {
                colQueue.removeAt(rowIdx)
                colQueue.addLast(0)
            }
        }
    }

    // 붙였으면 겹치기
    for (colQueue in deque) {
        for (idx in 0 until colQueue.lastIndex) {
            if (colQueue[idx] == 0) break
            if (colQueue[idx] != colQueue[idx + 1]) continue
            colQueue[idx] *= 2
            colQueue.removeAt(idx + 1)
            colQueue.addLast(0)
        }
    }

    // 덮어쓰기
    for (col in deque.indices) {
        for (row in deque[col].indices) {
            map[row][col] = deque[col][row]
        }
    }
}


fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val size = bufferedReader.readLine().toInt()

    val matrix = Array(size){
        bufferedReader.readLine().split(" ").map(String::toInt).toIntArray()
    }

    val map = Array(size){ArrayDeque<Int>(size)}

    // 테트리스처럼 0 을 삭제하며 앞뒤로 추가하기 위해 Deque 사용.
    for (row in matrix.indices) {
        for (col in matrix[row].indices) {
            map[row].addLast(matrix[row][col])
        }
    }

    var answer = 0

    val maxCaseCnt = 1 shl 10

    for (i in 0 until maxCaseCnt) {
        var num = i

        // 5번의 이동 완료
        for (flagCnt in 1 .. 5) {
            val directionNum = num % 4
            num /= 4

            when (directionNum) {
                Direction.EAST.ordinal -> moveRight(map)
                Direction.WEST.ordinal -> moveLeft(map)
                Direction.SOUTH.ordinal -> moveDown(map)
                Direction.NORTH.ordinal -> moveUp(map)
            }

        }

        // 라운드를 진행한 후 판에 적힌 숫자중 가장 큰 수 뽑아내기
        for (row in map) {
            answer = max(answer, row.maxOf { it })
        }

        // 라운드별 초기화
        for (row in matrix.indices) {
            for (col in matrix[row].indices) {
                map[row][col] = matrix[row][col]
            }
        }
    }

    print(answer)

}