프로그래머스 빛의 경로 사이클 Kotlin (시뮬레이션)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/86052

코딩테스트 연습 - 빛의 경로 사이클

문제 설명

각 칸마다 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

• 문제 예시와 같습니다.
• 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

• 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

• 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.

풀이

아우.. 월코챌 당시 문제가 이해가 안 가서 못 풀었던 문제다.(시간도 없었고)

사이클을 찾는 문제인데 dir을 반대 방향을 한 칸씩 띄워서, 즉, 상우하좌, 좌하우상 이런 식으로 저장하면 

    //d+3 %4 L
    //d+1 %4 R

이렇게 방향전환을 구현할 수 있다.

격자를 넘어갈 때 다음 칸의 좌표는

            nr = (nr + dir[nd][0]+n)%n
            nc = (nc + dir[nd][1]+m)%m

이렇게 구할 수 있다.

 

위의 두 가지 테크닉으로 탐색은 구현이 됐고, 이제 사이클을 찾아야 한다.

사이클을 찾기 위해선 현재 좌표에 4가지 방향 중 어떤 방향으로 다시 들어왔는지를 확인해야 한다.

따라서 visited[r][c][dir]로 모든 좌표의 4가지 방향에 대해 방문 체크를 한다.

 

나머지는 코드를 보면 쉽게 이해될 것이다.

이 그래프 내에서 사이클은 직접 시뮬레이션 몇 개 해보면 왜 이런 코드가 나오는지 알 수 있다.

 

전체적인 풀이는 다음과 같다.

1. 방문하지 않은 모든 좌표의 4방향에 대해 사이클이 있는지 탐색한다.

2. 탐색 도중 이미 방문했던 좌표의 방향을 다시 방문하면 현재 dis를 정답에 추가하고 탐색을 종료하고 다시 1번 과정으로 간다.

3. 정답 배열을 오름차순 정렬하여 리턴한다.

코드

class Solution {
    var resultArr = ArrayList<Int>()
    lateinit var visited: Array<Array<BooleanArray>>
    //상우하좌
    //d+3 %4 L
    //d+1 %4 R
    val dir = arrayOf(
        arrayOf(-1,0),
        arrayOf(0,1),
        arrayOf(1,0),
        arrayOf(0,-1)
    )
    fun simulation(grid: Array<String>, r: Int, c: Int, d: Int, n: Int, m: Int){
        var nr = r
        var nc = c
        var nd = d
        var dis = 0
        while(true){
            //check
            if(visited[nr][nc][nd]) break

            visited[nr][nc][nd] = true
            //next
            when(grid[nr][nc]){
                'L'-> nd = (nd+3)%4
                'R'-> nd = (nd+1)%4
                else-> {}
            }
            nr = (nr + dir[nd][0]+n)%n
            nc = (nc + dir[nd][1]+m)%m
            dis++

        }
        resultArr.add(dis)
    }

    fun solution(grid: Array<String>): IntArray {
        //solve
        //각 노드별 4방향 모두 탐색
        val n = grid.size
        val m = grid[0].length
        visited = Array(n){Array(m){BooleanArray(4)} }
        for(r in grid.indices){
            for(c in grid[r].indices){
                for(d in 0 until 4){
                    if(visited[r][c][d]) continue
                    simulation(grid,r,c,d,n,m)
                }
            }
        }
        //output
        return resultArr.sorted().toIntArray()
    }
}