[ 프로그래머스 - Java & Kotlin ] 빛의 경로 사이클 ( 자바 & 코틀린 )

( 월간 코드 챌린지 시즌3 / 빛의 경로 사이클 )

[문제]

문제 설명

각 칸마다 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'로 이루어져 있습니다.

입출력 예시

grid	result
["SL","LR"]	[16]
["S"]	[1,1,1,1]
["R","R"]	[4,4]

입출력 예 #1

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

입출력 예 #2

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

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

입출력 예 #3

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

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

---

[코드]

자바

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    // 상 우 하 좌 순서로 x, y좌표 더해줄 값 (방향 변수 d값이 아래 배열의 방향을 정함)
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    int w;  // 노드의 가로 크기
    int h;  // 노드의 세로 크기
    
    public int[] solution(String[] grid) {
        // 빛의 길이를 담을 배열
        ArrayList<Integer> arr = new ArrayList<>();
        w = grid[0].length();
        h = grid.length;
        // 가로세로 방문한 노드와 상 하 좌 우 방문 여부를 담은 배열
        boolean[][][] visit = new boolean[h][w][4];
        
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                for(int d = 0; d < 4; d++){
                    // 방문하지 않은 노드의 방향이 있을 경우
                    if(!visit[i][j][d]){
                        // 해당 노드부터 시작하는 빛의 길이를 계산후 반환
                        arr.add(getLightLen(grid, visit, i, j, d));
                    }
                }
            }
        }
        // 빛의 개수 만큼 배열 생성 후 빛의 길이 순서로 정렬
        int[] answer = new int[arr.size()];
        Collections.sort(arr);
        for(int i = 0; i < answer.length; i++) answer[i] = arr.get(i);
        
        return answer;
    }
    
    public int getLightLen(String[] grid, boolean[][][] visit, int y, int x, int d){
        int cnt = 0;    // 빛의 길이
        while(!visit[y][x][d]){
            cnt++;      // 빛의 길이 증가
            visit[y][x][d] = true;  // 현재 노드의 현재 방향 방문처리
            if(grid[y].charAt(x) == 'R') d = getDirection(d + 1);   // 방향 시계방향 회전
            else if(grid[y].charAt(x) == 'L') d = getDirection(d - 1);  // 방향 반시계방향 회전
            // 다음 방문할 위치계산 (중간에 배열의 크기를 더해서 음수가 되는것을 방지)
            x = (x + dx[d] + w) % w;    
            y = (y + dy[d] + h) % h; 
        }
        return cnt;
    }
    // 방향이 음수가 되거나 3을 넘어가면 보정해주는 기능
    public int getDirection(int direction){
        return direction < 0 ? 3 : direction % 4;
    }
}

코틀린

class Solution {
    // 상 우 하 좌 순서로 x, y좌표 더해줄 값 (방향 변수 d값이 아래 배열의 방향을 정함)
    val dx = intArrayOf(0, 1, 0, -1)
    val dy = intArrayOf(-1, 0, 1, 0)
    
    fun solution(grid: Array<String>): IntArray {
        // 빛의 길이를 담을 배열
        var answer = mutableListOf<Int>()
        // 가로세로 방문한 노드와 상 하 좌 우 방문 여부를 담은 배열
        val visit = Array<Array<BooleanArray>>(grid.size){
            Array<BooleanArray>(grid[it].length){ BooleanArray(4) }
        }
        
        for(i in visit.indices){
            for(j in visit[i].indices){
                for(d in visit[i][j].indices){
                    // 방문하지 않은 노드의 방향이 있을 경우 해당 노드부터 시작하는 빛의 길이를 계산후 반환
                    if(!visit[i][j][d]) answer.add(getLightLen(grid, visit, j, i, d))
                }
            }
        }
        // 빛의 개수 만큼 배열 생성 후 빛의 길이 순서로 정렬
        return answer.sorted().toIntArray()
    }
    
    fun getLightLen(grid:Array<String>, visit:Array<Array<BooleanArray>>, j:Int, i:Int, direction:Int):Int{
        var cnt = 0
        var x = j
        var y = i
        var d = direction
        
        while(!visit[y][x][d]){
            cnt++
            visit[y][x][d] = true   // 현재 노드의 현재 방향 방문처리
            when(grid[y][x]){
                'L' -> d = getDirection(d - 1)  // 방향 반시계방향 회전
                'R' -> d = getDirection(d + 1)  // 방향 시계방향 회전
            }
            // 다음 방문할 위치계산 (중간에 배열의 크기를 더해서 음수가 되는것을 방지)
            x = (x + dx[d] + grid[0].length) % grid[0].length
            y = (y + dy[d] + grid.size) % grid.size
        }
        
        return cnt
    }
    // 방향이 음수가 되거나 3을 넘어가면 보정해주는 기능
    fun getDirection(d:Int) = if(d < 0) 3 else d % 4
}

문제 링크

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

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄