17780번: 새로운 게임 (Kotlin)

제한사항

• 4 ≤ N ≤ 12
• 4 ≤ K ≤ 10

문제 정리

체스판의 크기는 N * N

체스판의 칸의 색깔은 흰색, 빨간색, 파란색 중 하나

말은 1~K번까지 있다.

말 위에 말을 올릴 수 있다.

이동 방향은 위, 아래, 왼쪽, 오른쪽 4방향

턴마다 모든 말이 번호 순서대로 이동한다.

한 말이 이동할 때 위에 말도 동시에 이동하며, 가장 아래에 있는 말만 이동할 수 있다.

말이 4개 이상 쌓이면 게임 종료

접근 방법

구현 문제인데 생각보다 굉장히 까다로웠습니다.

map을 이용해서 key값을 말의 번호, value를 tower로 했습니다.

복잡도

시간복잡도 : O(1000*k) → O(k) → 1000은 문제에서 주어진 제한 횟수이다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.HashMap

class HorseTower(var row: Int, var col: Int, horse: Horse) {
    private val horseTower = LinkedList<Horse>()

    fun getBottomHorse(): Horse = horseTower.first

    fun getTowerHeight() = horseTower.size

    fun reverseTower() = horseTower.reverse()

    fun stackHorse(horse: Horse) = horseTower.add(horse)

    fun stackTower(horseTower: HorseTower) {
        for (i in 0 until horseTower.horseTower.size) {
            stackHorse(horseTower.horseTower[i])
        }
    }

    init {
        horseTower.add(horse)
    }
}

class Horse(val no: Int, private var directionIdx: Int) {
    companion object {
        val directions = arrayOf(0 to 1, 0 to -1, -1 to 0, 1 to 0)
    }

    fun getDirection() = directions[directionIdx]

    fun reverseDirection() {
        directionIdx = when (directionIdx) {
            0 -> 1
            1 -> 0
            2 -> 3
            3 -> 2
            else -> 0
        }
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, k) = readLine().split(" ").map { it.toInt() }
    val map = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }
    val horseMap = Array(n) { Array<HorseTower?>(n) { null }}

    // Key를 가장 밑에 말의 번호로 Value를 말 전체
    val horseTowerMap = HashMap<Int, HorseTower>()
    repeat(k) { horseNo ->
        val (row, col, directionIdx) = readLine().split(" ").map { it.toInt() }
        val horse = Horse(horseNo + 1, directionIdx - 1)
        val horseTower = HorseTower(row - 1, col - 1, horse)
        horseMap[row - 1][col - 1] = horseTower
        horseTowerMap[horseNo + 1] = horseTower
    }

    var turn = 0
    do {
        turn++
        for (i in 1..k) {
            val tower = horseTowerMap[i] ?: continue

            val bottomHorse = tower.getBottomHorse()
            val towerRow = tower.row
            val towerCol = tower.col
            var towerDirection = bottomHorse.getDirection()

            var nextTowerRow = tower.row + towerDirection.first
            var nextTowerCol = tower.col + towerDirection.second

            // 파란색이거나 맵 밖이면
            if (nextTowerRow !in 0 until n || nextTowerCol !in 0 until n || map[nextTowerRow][nextTowerCol] == 2) {
                // 방향을 바꾼 후에
                bottomHorse.reverseDirection()
                towerDirection = bottomHorse.getDirection()
                nextTowerRow = towerRow + towerDirection.first
                nextTowerCol = towerCol + towerDirection.second

                // 그래도 맵 밖이면 넘어간다.
                if (nextTowerRow !in 0 until n || nextTowerCol !in 0 until n || map[nextTowerRow][nextTowerCol] == 2) {
                    continue
                } else if (map[nextTowerRow][nextTowerCol] == 1) {
                    tower.reverseTower()
                }

                if (horseMap[nextTowerRow][nextTowerCol] == null) {
                    horseMap[nextTowerRow][nextTowerCol] = tower
                    horseMap[towerRow][towerCol] = null
                } else {
                    horseMap[nextTowerRow][nextTowerCol]!!.stackTower(tower)
                    horseMap[towerRow][towerCol] = null
                }

                tower.row = nextTowerRow
                tower.col = nextTowerCol
                horseTowerMap.remove(bottomHorse.no)
                horseTowerMap[horseMap[nextTowerRow][nextTowerCol]!!.getBottomHorse().no] = horseMap[nextTowerRow][nextTowerCol]!!
            } else {
                if (map[nextTowerRow][nextTowerCol] == 1) {
                    tower.reverseTower()
                }

                if (horseMap[nextTowerRow][nextTowerCol] == null) {
                    horseMap[nextTowerRow][nextTowerCol] = tower
                    horseMap[towerRow][towerCol] = null
                } else {
                    horseMap[nextTowerRow][nextTowerCol]!!.stackTower(tower)
                    horseMap[towerRow][towerCol] = null
                }

                tower.row = nextTowerRow
                tower.col = nextTowerCol
                horseTowerMap.remove(bottomHorse.no)
                horseTowerMap[horseMap[nextTowerRow][nextTowerCol]!!.getBottomHorse().no] = horseMap[nextTowerRow][nextTowerCol]!!
            }
        }

        if (horseTowerMap.values.any { it.getTowerHeight() >= 4 }) {
            println(turn)
            return
        }
    } while (turn < 1000)

    println(-1)
}