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

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

제한사항

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

Code

import java.util.*;
class Solution {
    public int[] solution(String[] grid) {
        int m=grid.length, n=grid[0].length();
        
        String[][] map = new String[m][n];
        for(int i=0 ; i<m ; i++) {
            map[i] = grid[i].split("");
        }

        boolean[][][] visit = new boolean[m][n][4];
        
        // U:0, D:1, L:2, R:3
        Map<String, int[][]> dir = new HashMap<>();
        // cur, point by before
        dir.put("S", new int[][]{{-1,0},{1,0},{0,-1},{0,1}});
        dir.put("R", new int[][]{{0,1},{0,-1},{-1,0},{1,0}});
        dir.put("L", new int[][]{{0,-1},{0,1},{1,0},{-1,0}});

        List<Integer> list = new ArrayList<>();

        Map<String, int[]> next = new HashMap<>();
        // curr, next step array
        next.put("S", new int[]{0,1,2,3});
        next.put("R", new int[]{3,2,0,1});
        next.put("L", new int[]{2,3,1,0});

        for(int i=0 ; i<m ; i++) {
            for(int j=0 ; j<n ; j++) {
                int stepI=i, stepJ=j;
                // U:0, D:1, L:2, R:3
                for(int k=0 ; k<4 ; k++) {
                    int cnt = 0, d=k;
                    while(!visit[stepI][stepJ][d]) {
                        visit[stepI][stepJ][d] = true;
                        cnt++;
                        int nxt = next.get(map[stepI][stepJ])[d];
                        int[] s = dir.get(map[stepI][stepJ])[d];
                        stepI = (stepI+s[0]+m)%m;
                        stepJ = (stepJ+s[1]+n)%n;
                        d = nxt;
                    }
                    if(cnt>0) list.add(cnt);
                }
            }
        }

        Collections.sort(list);
        int[] ret = new int[list.size()];
        for(int i=0 ; i<list.size() ; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

Comment

1. recursive로 풀었더니 런타임 오류 걸리는 케이스가 하나 있었다. 그래서 반복문으로 변경했다.
2. visit을 Set으로 했는데 위 이유 때문에 싹 지우고 처음부터 풀었을때 그냥 한번 배열로 해봤다.
3. 그래도 안되어서 보니까 정렬을 빼먹었다. 근데 또 안된다. 보니까 오름차순이더라. 진짜 문제 좀 잘보자!