[프로그래머스 Level.2] 빛의 경로 사이클 (월간 코드 챌린지 시즌3) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌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.*;

class Solution {
    boolean[][][] visited;
    // 방향 변수 d값이 아래 배열의 방향을 정함
    int[] dx = {0, -1, 0, 1}; // 하 좌 상 우
    int[] dy = {-1, 0, 1, 0};
    public int[] solution(String[] grid) {
        int[] answer;
        
        char[][] matrix = new char[grid.length][grid[0].length()];
        visited = new boolean[matrix.length][matrix[0].length][4]; // 마지막 크기 4는 아래부터 시계방향
        ArrayList<Integer> list = new ArrayList<>();
        
        for(int i=0; i<grid.length; i++) {
            for(int j=0; j<grid[i].length(); j++) {
                matrix[i][j] = grid[i].charAt(j);
            }
        }
        
        for(int i=0; i<visited.length; i++) {
            for(int j=0; j<visited[0].length; j++) {
                for(int k=0; k<visited[0][0].length; k++) {
                    if(!visited[i][j][k]) {
                        int cycleLength = getCycleLength(i, j, k);
                        list.add(cycleLength);
                    }
                }
            }
        }
        
        answer = new int[list.size()];
        
        Collections.sort(list);
        
        for(int i=0; i<list.size(); i++) {
            answer[i] = list.get(i);
        }
        
        return answer;
    }
    
    public int getCycleLength(char[][] matrix, int x, int y, int d) {
        int cnt = 0;
        
        while(!visited[x][y][d]) {
            visited[x][y][d] = true;
            cnt++;
            
            if(matrix[x][y] == 'L')
                d = (d == 0 ? 3 : d - 1);
			
            if(matrix[x][y] == 'R')
                d = (d == 3 ? 0 : d + 1);
            
            // 다음 방문할 위치계산 (중간에 배열의 크기를 더해서 음수가 되는것을 방지)
            x = (x + dy[d] + matrix.length) % matrix.length;
            y = (y + dx[d] + matrix[0].length) % matrix[0].length;
        }
        
        return cnt;
    }
}

 

풀이

1. 이 문제는 사이클의 개수를 구하는 문제인데 처음에 너무 헷갈렸다.. 어디서 시작하든 같은 이동 경로를 통해 반복하게 된다면 그게 사이클이다... 즉, 결국 문제에 주어진 것처럼 사이클의 이동 경로에 숫자는 중요하지 않고 해당 경로와 같은 경로로 계속해서 반복 순환하는 경로라면 그게 한 가지의 사이클이다.
2. 따라서 하나의 경로는 모든 사이클에서 한 가지이기 때문에 한 격자로 들어오는 방향으로 4방향을 모두 확인하면 모든 사이클에서 한 가지만 있게 된다. 어차피 나가는 방향은 어디로든 들어오는 방향과 짝이되어 하나이기 때문에 들어오는 4방향만 확인하면 된다. 결국 4방향까지 추가한 visited를 하나 만들고 경로를 true로 변경하며 모두 true가 될 때까지 모든 사이클을 구하면 된다.
3. 격자의 각 칸을 나타내기 위한 2차원 char형 배열 matrix를 생성하고 해당 격자에서 하좌상우 4방향까지 포함한 3차원 배열 visited를 생성한다. 그리고 격자에서 하좌상우로 한 칸씩 이동하기 위해 int형 배열 dx와 dy를 생성한다.
4. 사이클을 발견했을 때 사이클의 길이를 담아주기 위한 list를 생성하고 주어진 String 배열 grid를 for문을 돌면서 toCharArray()를 이용하여 char형 2차원 배열 matrix에 담아준다.
5. 그리고 3차원 배열 visited를 모두 탐색하기 위해 3중 for문을 만들고 visited를 탐색하면서 visited가 false일 때마다 해당 사이클의 경로 길이를 구하도록 한다.
6. 해당 사이클의 경로 길이를 구하기 위해 int 타입 cnt를 선언하고 visited가 true가 나올 때까지 while문을 반복한다.
7. 해당 격자의 방향인 visited를 true로 하고 cnt를 증가시킨다. 그리고 다음 격자와 방향을 구하고 다음 격자의 방향이 visited가 true일 때까지 반복문을 진행하면 카운팅한 cnt가 한 사이클의 경로 길이가 된다.
8. 반복문을 진행할 때 다음 격자의 좌표와 방향을 구하는 것이 중요하다. 우선 나는 0인덱스부터 3인덱스까지 아래부터 시계방향으로 4방향을 두었다.(하 - 0, 좌 - 1, 상 - 2, 우 - 3)
   하 (0) : (위에서) 아래 방향으로 해당 격자로 들어온 것
   좌 (1) : (오른쪽에서) 왼쪽 방향으로 해당 격자로 들어온 것
   상 (2) : (아래에서) 위 방향으로 해당 격자로 들어온 것
   우 (3) : (왼쪽에서) 오른쪽 방향으로 해당 격자로 들어온 것
   예를 들어 visited[0][0][0]은 0열 0행에 있는 격자에 (위에서) 아래 방향으로 해당 격자로 들어온 것이고 visited[0][1][2]는 0열 1행에 있는 격자에 (아래에서) 위로 들어오는 방향으로 해당 격자에 온 것이다.
9. 이렇게 들어오는 방향으로 했기 때문에 해당 좌표의 matrix 값(S or L or R)에 따라 다음 좌표와 방향을 구할 수 있다.
10. 다음 방향의 경우 해당 좌표가 'L'이라면 다음과 같다.
    (위쪽에서) 아래 방향으로 들어왔을 경우(0) 오른쪽 방향으로 가야 하기 때문에 다음 방향은 3
    (왼쪽에서) 오른쪽 방향으로 들어왔을 경우(3) 위쪽 방향으로 가야 하기 때문에 다음 방향은 2
    (아래쪽에서) 위 방향으로 들어왔을 경우(2) 왼쪽 방향으로 가야 하기 때문에 다음 방향은 1
    (오른쪽에서) 왼쪽 방향으로 들어왔을 경우(1) 아래쪽 방향으로 가야 하기 때문에 다음 방향은 0
11. 이렇게 따져보면 0인 경우 3으로 나머지는 d-1을 하면 다음 방향을 알 수 있다. 마찬가지로 'R'일 경우를 따지면 3인 경우는 0으로 나머지는 d+1을 하면 다음 방향을 알 수 있다.
12. 다음 좌표는 다음 좌표가 들어오는 방향을 구했으니 그 방향의 값 인덱스로 dx, dy에 해당하는 값을 x + dy[i] , y+ dx[i]를 이용하여 구하면 된다. 해당 좌표에서 방향의 값(음수 포함)을 더했을 때 음수가 되는 경우를 방지하기 위해서 해당 좌표의 값에 행에는 행의 크기 열에는 열의 크기를 더하고 마지막 좌표에서 마지막 행에서 다음 행은 첫 행이 되고 마지막 열에서 다음 열은 첫 열이 되므로 각각 행과 열로 나누어 주도록 한다.
13. 이렇게 각 격자를 이동하며 해당 방향을 true로 변경하며 해당 사이클 경로의 길이를 카운팅하고 카운팅한 수를 리스트에 추가하며 모든 사이클의 경로 길이를 구한 후 리스트를 오름차순으로 정렬하고 answer에 담은후 반환한다.