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

🔗 https://school.programmers.co.kr/tryouts/74944/

문제 정보

※ 자세한 문제에 대한 정보의 위의 링크를 참조해주세요!

제한 사항

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

문제 요약

문제에서 요구한 사항을 요약하면 다음과 같습니다.

1. 격자에 ‘S’가 있으면 이전 방향 그대로 직진.
2. 격자에 ‘L’이 있으면 좌회전.
3. 격자에 ‘R’이 있으면 우회전.
4. 격자 밖으로 나가면 0으로 이동 (순환되는 구조).

이러한 요구 사항이 주어졌을 때, 순환되는 경로의 길이를 배열로 받아서 오름차순으로 정렬 후 반환해야합니다.

문제 풀이

맨 처음 문제를 보고 들었던 생각은 아래와 같습니다.

1. 각 격자마다 4개 방향에 대해서 방문 여부를 체크해야할 것 같다.
2. 이전에 나왔던 사이클이 다른 더 큰 사이클의 작은 사이클로 포함될 수 있을까? 혹은 이전에 나왔던 사이클이 다른 격자에서 출발해도 생길 수 있을까?

1번을 생각한 이유는 순환이 되는지를 확인하기 위해선 이전에 이 격자에 와봤는지 뿐만 아니라 이 방향으로 가본 적이 있는지를 체크해야 해당 격자에서 다른 방향으로도 이동할 수 있겠다는 생각때문 이었습니다.

2번을 생각한 이유는 만약 이게 계속 이후에도 같은 사이클이 등장할 수 있다면 완전탐색으로 풀면 뭔가 시간제한에 걸릴 수 있겠다고 생각을 했습니다. 그래서 저 질문을 생각을 해보니까 일단 각 격자마다 들어가 있는 값은 'L', 'R', 'S' 로 고정되어 있습니다. 그렇다는 것은 경로가 고정되어 있다는 것이기에 이전 사이클이 다음 사이클에 포함될 수 없습니다. 하나의 사이클에 포함되는 격자와 방향에 포함되기만 하면 아마 해당 사이클을 돌 때 순회를 할 것이고 그 때 방문 체크를 할 것이기 때문에 다시 나오는 것이 불가능합니다. 그리고 만약 어디론가 쐈는데 다시 돌아오지 않는 경우가 있으면?? 이 경우는 없습니다. 이런 경우가 존재하면 문제를 풀 수 없는 경우도 생기기 때문에 무조건 어디론가 쏘면 다시 돌아온다고 생각하고 접근하면 됩니다.

문제 코드

import java.util.*;

class Solution {
    
    private static final int DIR_NUM = 4, MAX_SIZE = 500;
    private int r, c;
    
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private boolean[][][] visited = new boolean[MAX_SIZE][MAX_SIZE][DIR_NUM];
    private int[][] value = new int[MAX_SIZE][MAX_SIZE];
    
    private List<Integer> result = new ArrayList<>();
    
    public int[] solution(String[] grid) {
        initialize(grid);
        move();
        int[] answer = result.stream()
            .mapToInt(i -> i)
            .toArray();
        Arrays.sort(answer);
        return answer;
    }
    
    private void initialize(String[] grid) {
        r = grid.length;
        c = grid[0].length();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i].charAt(j) == 'S') {
                    value[i][j] = 0;
                } else if(grid[i].charAt(j) == 'L') {
                    value[i][j] = 1;
                } else {
                    value[i][j] = -1;
                }
            }
        }
    }
    
    private void move() {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < DIR_NUM; k++) {
                    if (!visited[i][j][k]) {
                        result.add(moveRoute(i, j, k));
                    }
                }
            }
        }
    }
    
    private int moveRoute(int x, int y, int d) {
        int cnt = 0;
        int nowX = x;
        int nowY = y;
        int nowD = d;
        while(true) {
            
            if (visited[nowX][nowY][nowD]) break;
          
            cnt++;
            visited[nowX][nowY][nowD] = true;
            
            int nx = (nowX + dx[nowD] + r) % r;
            int ny = (nowY + dy[nowD] + c) % c;
            
            int nd = (DIR_NUM + nowD + value[nx][ny]) % DIR_NUM;
            
            nowX = nx;
            nowY = ny;
            nowD = nd;
        }
        
        return cnt;
    }
}