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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/86052

프로그래머스

 

---

 

문제 설명

격자(grid)에서 빛이 이동할 수 있는 경로 사이클을 찾는 문제입니다. 각 칸에는 'S', 'L', 'R' 중 하나가 써져 있으며, 빛이 이동할 때 다음과 같은 규칙을 따릅니다:

• 'S': 빛은 직진합니다.
• 'L': 빛은 좌회전합니다.
• 'R': 빛은 우회전합니다.

격자에서 빛이 이동할 때 경계를 넘어갈 경우 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 위쪽 가장자리를 벗어날 경우 같은 열의 맨 아래쪽에서 다시 시작합니다.

이 문제의 목표는 격자에서 빛이 이동하여 원래 위치로 돌아올 때까지의 경로(사이클)를 찾아 그 길이를 반환하는 것입니다. 가능한 모든 사이클을 찾고, 그 길이를 오름차순으로 정렬하여 반환해야 합니다.

접근 방법

1. 방향 설정: 빛이 이동할 수 있는 방향은 상(0), 좌(1), 하(2), 우(3) 네 가지입니다. 각 방향에 대해 이동할 때의 좌표 변화(델타 값)를 설정합니다.
2. 방문 여부 기록: 격자 내 각 칸에서 각 방향으로의 방문 여부를 기록하기 위해 3차원 배열 isVisited를 사용합니다.
3. 순환 경로 탐색:
   • 격자의 각 칸과 각 방향에서 출발하여 빛이 이동하는 경로를 추적합니다.
   • 빛이 이동할 때 S, L, R에 따라 방향을 변경하며 다음 칸으로 이동합니다.
   • 격자를 벗어날 경우 반대쪽 끝으로 이동합니다.
4. 사이클 탐지:
   • 빛이 이미 방문한 칸과 방향으로 돌아오면 사이클이 완성된 것으로 판단하고 그 길이를 기록합니다.
5. 결과 반환:
   • 모든 경로 탐색이 끝난 후 각 사이클의 길이를 오름차순으로 정렬하여 반환합니다.

import java.util.ArrayList;

class Solution {
    static int R, C;
    // 상, 좌, 하, 우 방향
    static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 }; 
    static boolean[][][] isVisited;

    public int[] solution(String[] grid) {
        ArrayList<Integer> answer = new ArrayList<>();
        R = grid.length;
        C = grid[0].length();

        // 방문 여부를 기록하는 3차원 배열 (행, 열, 방향)
        isVisited = new boolean[R][C][4];

        // 모든 좌표와 모든 방향에 대해 경로를 탐색
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                for (int d = 0; d < 4; d++) {
                    if (!isVisited[i][j][d]) {
                        answer.add(light(grid, i, j, d));
                    }
                }
            }
        }

        // 결과를 오름차순으로 정렬하여 반환
        return answer.stream().sorted().mapToInt(i -> i).toArray();
    }

    private static int light(String[] grid, int r, int c, int d) {
        int cnt = 0; // 사이클의 길이

        while (true) {
            // 이미 방문한 경로라면 종료
            if (isVisited[r][c][d]) break;

            cnt++; // 이동한 거리 증가
            isVisited[r][c][d] = true; // 방문 기록

            // 현재 칸의 문자에 따라 방향 전환
            if (grid[r].charAt(c) == 'L')
                d = d == 0 ? 3 : d - 1; // 좌회전
            else if (grid[r].charAt(c) == 'R')
                d = d == 3 ? 0 : d + 1; // 우회전

            // 다음 위치 계산 (경계를 넘어갈 경우 반대쪽으로 이동)
            r = (r + dr[d] + R) % R;
            c = (c + dc[d] + C) % C;
        }

        return cnt; 
    }
}