programmers_빛의 경로 사이클_java

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

프로그래머스

import java.util.*;

class Solution {
   private static int[][] delta = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, }; // 우, 하, 좌, 상

    public int[] solution(String[] grid) {
        int[] answer = {};

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

        Set<Node> nodes = new HashSet<>();
        for (int i = 0; i<grid.length; i++){
            for (int j = 0; j<grid[i].length(); j++){
                for (int d = 0; d<4; d++){
                    if (!nodes.contains(new Node(i, j, d))){
                        int res = findCycle(i, j, d, nodes, grid);
                        answerList.add(res);
                    }
                }
            }
        }

        // list to array
        answer = new int[answerList.size()];
        for (int i = 0; i<answerList.size(); i++){
            answer[i] = answerList.get(i);
        }

        // 오름차순 정렬
        Arrays.sort(answer);

        return answer;
    }

    public int findCycle(int y, int x, int dir, Set<Node> nodes, String[] grid){
        int cnt = 0;
        Node now = new Node(y, x, dir);

        while (true){
            if (nodes.contains(now)){ // 사이클 발생
                return cnt;
            }
            nodes.add(now);
            int[] next = move(grid, now.y, now.x, now.dir);
            now = new Node(next[0], next[1], next[2]);
            cnt++;
        }
    }

    // StackOverFlow 에러 발생 - 재귀가 너무 많아 발생
//    public static int dfs(int y, int x, int dir, int cnt, Set<Node> nodes, String[] grid){
//        Node now = new Node(y, x, dir);
//        if (nodes.contains(now)){ // 사이클 발생
//            return cnt;
//        }
//
//        // 방문처리
//        nodes.add(now);
//        int[] next = move(grid, y, x, dir);
//        return dfs(next[0], next[1], next[2], cnt+1,  nodes, grid);
//    }

    public int[] move(String[] grid, int y, int x, int dir){

        // 방향 전환
        if (grid[y].charAt(x) == 'R'){
            dir = (dir == 3 ? 0 : dir+1);
        }else if (grid[y].charAt(x) == 'L'){
            dir = (dir == 0 ? 3 : dir-1);
        }
        // +grid.lenth : 음수로 되는 경우 방지
        int nexyy = (y + delta[dir][0] + grid.length) % grid.length;
        int nexyx = (x + delta[dir][1] + grid[y].length()) % grid[y].length();

        int[] next = new int[]{nexyy, nexyx, dir};

        return next;
    }

    public class Node{
        int y,  x, dir;
        public Node(int y, int x, int dir){
            this.y = y;
            this.x = x;
            this.dir = dir;
        }

		// set에서 비교하기 위해 작성
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return y == node.y && x == node.x && dir == node.dir;
        }

        @Override
        public int hashCode() {
            return Objects.hash(y, x, dir);
        }
    }
}