백준 14891 톱니바퀴 - Kotlin

https://www.acmicpc.net/problem/14891
난이도: 골드5

단순한 구현 문제이긴한데 뭔가 첫인상이 복잡해보이네요. 하나씩 봅시다

총 4개의 톱니바퀴가 있습니다. 간단하게 설명하면, 4개중 하나의 톱니바퀴를 선택하여 시계방향 또는 반시계방향으로 돌릴겁니다. 그런데 이웃된 톱니바퀴와 닿아있는 부분이 서로 다른 극이라면, 회전한 톱니바퀴와 반대 방향으로 이웃된 톱니바퀴가 회전됩니다.

먼저 Input을 받겠습니다.

val list = mutableListOf<MutableList<Int>>()
repeat(4) {
    list.add(readLine()!!.map { it - '0' }.toMutableList())
}

저는 귀찮아서 BufferedReader같은 클래스로 안쓰고 그냥 readLine()!!으로 씁니다. 가끔 느려서 타임아웃 나는 문제가 있으니 주의해야합니다.

그리고 회전을 담당하는 메소드인 rotate() 메소드를 구현할 것인데요, 몇번째 index의 톱니를 회전시킬지와 회전 방향인 direction을 parameter로 받았습니다.

fun rotate(targetIndex: Int, direction: Int) {
	// TODO
}

그리고 이 리스트를 회전시켜주는 circularShift와, 반대 방향을 쉽게 나타내기 위해서 reverseDirection이라는 확장함수를 정의했습니다.

fun Int.reverseDirection(): Int = when (this) {
    1 -> -1
    -1 -> 1
    else -> throw Exception()
}

fun MutableList<Int>.circularShift(direction: Int) {
    if (isEmpty()) return
    when (direction) {
        1 -> {
            val lastElement = removeLast()
            add(0, lastElement)
        }

        -1 -> {
            val firstElement = removeFirst()
            add(firstElement)
        }
    }
}

이제 이웃된 톱니바퀴를 회전시킬지를 결정해야 하는데요, 왼쪽 톱니의 경우 현재 톱니의 6 번 인덱스와 왼쪽 톱니의 2번 인덱스를 비교하여 회전 시킬지 말지를 결정할 수 있습니다. 그리고 이미 회전시킨 톱니는 다시 회전 시키지 않도록 isDone 이라는 크기 4의 BooleanArray를 선언했습니다.

fun canRotateLeft(targetIndex: Int, left: Int) =
    targetIndex - 1 >= 0 && !isDone[targetIndex - 1] && left != list[targetIndex - 1][2]

아래와 같은 과정으로 왼쪽 톱니를 회전시킬지 말지 결정합니다.

1. targetIndex의 왼쪽 톱니가 존재하는지 판단합니다 targetIndex - 1 >= 0
2. 이미 회전된 톱니인지 판단합니다 !isDone[targetIndex - 1]
3. 닿아있는 부분이 서로 다른 극인지 확인합니다. left != list[targetIndex - 1][2]

반대 과정으로 오른쪽 톱니를 회전할지도 결정합니다.

fun canRotateRight(targetIndex: Int, right: Int) =
	targetIndex + 1 < 4 && !isDone[targetIndex + 1] && right != list[targetIndex + 1][6]

따라서, rotate함수는 아래와 같이 구성할 수 있습니다.

fun rotate(targetIndex: Int, direction: Int) {
    val left = list[targetIndex][6]
    val right = list[targetIndex][2]
    list[targetIndex].circularShift(direction)
    isDone[targetIndex] = true
    if (canRotateLeft(targetIndex, left)) {
        rotate(targetIndex - 1, direction.reverseDirection())
    }
    if (canRotateRight(targetIndex, right)) {
        rotate(targetIndex + 1, direction.reverseDirection())
    }
}

1. 회전 시키기 전, 왼쪽과 닿은 부분과 오른쪽과 닿은 부분의 값을 left, right로 저장합니다.
2. 주어진 방향으로 현재 톱니를 회전시킵니다.
3. 회전되었음을 표기합니다.
4. 좌, 우 각각 회전 가능한지 확인하고 가능하다면 회전시킵니다.

따라서 전체 코드는 아래와 같습니다.

fun main() {
    val list = mutableListOf<MutableList<Int>>()
    repeat(4) {
        list.add(readLine()!!.map { it - '0' }.toMutableList())
    }

    val isDone = BooleanArray(4) { false }

    fun canRotateLeft(targetIndex: Int, left: Int) =
        targetIndex - 1 >= 0 && !isDone[targetIndex - 1] && left != list[targetIndex - 1][2]

    fun canRotateRight(targetIndex: Int, right: Int) =
        targetIndex + 1 < 4 && !isDone[targetIndex + 1] && right != list[targetIndex + 1][6]

    fun rotate(targetIndex: Int, direction: Int) {
        val left = list[targetIndex][6]
        val right = list[targetIndex][2]
        list[targetIndex].circularShift(direction)
        isDone[targetIndex] = true
        if (canRotateLeft(targetIndex, left)) {
            rotate(targetIndex - 1, direction.reverseDirection())
        }
        if (canRotateRight(targetIndex, right)) {
            rotate(targetIndex + 1, direction.reverseDirection())
        }
    }

    repeat(readLine()!!.toInt()) {
        val (idx, direction) = readLine()!!.split(" ").map { it.toInt() }
        rotate(idx - 1, direction)
        isDone.fill(false)
    }

    var answer = 0
    list.forEachIndexed { index, ints ->
        when (index) {
            0 -> answer += ints[0]
            1 -> answer += ints[0] * 2
            2 -> answer += ints[0] * 4
            3 -> answer += ints[0] * 8
        }
    }
    println(answer)
}

fun Int.reverseDirection(): Int = when (this) {
    1 -> -1
    -1 -> 1
    else -> throw Exception()
}

fun MutableList<Int>.circularShift(direction: Int) {
    if (isEmpty()) return
    when (direction) {
        1 -> {
            val lastElement = removeLast()
            add(0, lastElement)
        }

        -1 -> {
            val firstElement = removeFirst()
            add(firstElement)
        }
    }
}

조금 복잡하게 풀이한것 같기도 하네요. 풀이시간은 대략 25분 정도 소요됐습니다