[Kotlin] 프로그래머스 - 빛의 경로 사이클

문제

링크

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ grid의 길이 ≤ 500

• 1 ≤ grid의 각 문자열의 길이 ≤ 500
• grid의 모든 문자열의 길이는 서로 같습니다.
• grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

입출력 예

입출력 예 #1

• 입력: ["SL","LR"]
• 출력: [16]

입출력 예 #2

• 입력: ["S"]
• 출력: [1,1,1,1]

입출력 예 #3

• 입력: ["R","R"]
• 출력: [4,4]

풀이

알고리즘보다는 문제에 대한 이해도와 배열 활용도를 요구하는 문제

1. 빛을 임의의 위치(네 방향, 상하좌우)에서 쐈을 때 사이클 하나가 어떻게 발생하는지 이해하기

• 빛은 주어진 격자(grid) 요소(SRL)에 따라 이동하다가 원래 위치로 되돌아온다.
• 빛이 제자리로 돌아오면 사이클 하나가 종료된다.
• 다른 사이클이 통과한 경로는 이용하지 않는다. (중복되는 순간부터 이전 사이클과 동일해진다.)
• 무한 이동하지 않도록 격자 요소마다 네 방향을 들렀는지 여부를 알고 있어야 한다.
• [x좌표][y좌표][방향]을 가지는 3차원 배열 변수 설정 (visible)

2. 격자 요소마다 빛을 네 방향 모두 쏴봐야하므로 회전 방향을 정한다.

• 회전 방향을 정하여 x, y 이동 좌표 변수 설정 (*_axis_direction)
• x, y축을 그려서 이동 좌표 변수를 확인해보면 '다음 index = (현재 index + index 0에서 회전하면 나오는 index) % 변수 길이'

3. 회전 했을 때 좌표가 변하는 규칙 찾기

• 빛이 격자 밖으로 이동하면 반대쪽 끝으로 돌아온다.
• 다음 축 위치 = (현재 축 위치 + 회전 방향 + 축 길이) % 축 길이

코드

class Solution {
    private val xAxisDir = arrayOf(0, -1, 0, 1)
    private val yAxisDir = arrayOf(-1, 0, 1, 0)

    private val directionCount = 4
    private var rowCount: Int = 0
    private var colCount: Int = 0
    
    private lateinit var visible: Array<Array<BooleanArray>>
    
    fun solution(grid: Array<String>): IntArray {
        rowCount = grid.size
        colCount = grid[0].length

        visible = Array(rowCount) { Array(colCount) { BooleanArray(directionCount) { false } } }

        val answer = ArrayList<Int>()

        for (y in 0 until rowCount) {
            for (x in 0 until colCount) {
                for (d in 0 until directionCount) {
                    if (visible[y][x][d]) continue
                    answer.add(lightCycle(grid, y, x, d))
                }
            }
        }

        return answer.sorted().toIntArray()
    }

    private fun lightCycle(grid: Array<String>, row: Int, col: Int, direction: Int): Int {
        var lightLength = 0
        var (y, x, d) = Triple(row, col, direction)
        while (!visible[y][x][d]) {
            lightLength++
            visible[y][x][d] = true

            d = rotation(grid[r][c], d)
            y = (y + yAxisDir[d] + rowCount) % rowCount
            x = (x + xAxisDir[d] + colCount) % colCount
        }
        return lightLength
    }

    private fun rotation(direction: Char, entryDirection: Int): Int {
        return when (direction) {
            'L' -> (entryDirection + 3) % 4
            'R' -> (entryDirection + 1) % 4
            else -> entryDirection
        }
    }
}

테스트 1 〉	통과 (25.04ms, 63.3MB)
테스트 2 〉	통과 (21.85ms, 64.1MB)
테스트 3 〉	통과 (16.41ms, 64.8MB)
테스트 4 〉	통과 (31.90ms, 63.3MB)
테스트 5 〉	통과 (31.95ms, 66.2MB)
테스트 6 〉	통과 (35.99ms, 64.5MB)
테스트 7 〉	통과 (109.65ms, 77.7MB)
테스트 8 〉	통과 (82.17ms, 71.7MB)
테스트 9 〉	통과 (79.79ms, 100MB)
테스트 10 〉	통과 (87.28ms, 101MB)
테스트 11 〉	통과 (88.31ms, 102MB)