월간 코드 챌린지 시즌3 / 빛의 경로 사이클

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

프로그래머스

정답률에 비해 풀이법이 간단해서 금방 풀 줄 알았지만..

하필이면 첫줄 방향 벡터에 오타가 발생해서 찾는데 오래 걸린데다가

첫 풀이에선 재귀 형식으로 코드를 작성했는데 7번 케이스에서 함수 호출 스택이 넘쳐서 while문으로 교체하고나니 시간이 금방 지나갔네요..

실제 코딩테스트 상황이었으면 대참사였을 것 같습니다.

import java.util.ArrayList;

class Solution {
    private static final int[][] MOVES = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private Node[][] board;
    private final ArrayList<Integer> result = new ArrayList<>();
    
    private Node node = null;
    private int outputDirectionIndex = -1;
    
    public int[] solution(String[] grid) {
        init(grid);
        
        for (Node[] nodes : board) {
            for (Node node : nodes) {
                go(node);
            }
        }
        
        result.sort(null);

        return result.stream().mapToInt(i -> i).toArray();
    }

    private void init(String[] grid) {
        board = new Node[grid.length][grid[0].length()];

        for (int row = 0; row < grid.length; row++) {
            String line = grid[row];
            for (int col = 0; col < line.length(); col++) {
                char direction = line.charAt(col);
                int[] outputs = {0, 0, 0, 0};
                board[row][col] = new Node(direction, outputs);
            }
        }

        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                board[row][col].nextNodes = getNextNodes(row, col);
            }
        }

    }

    private Node[] getNextNodes(int row, int col) {
        Node[] nodes = new Node[4];

        for (int directionIdx = 0; directionIdx < MOVES.length; directionIdx++) {
            int[] coordinate = getNextCoordinate(row, col, MOVES[directionIdx]);
            nodes[directionIdx] = board[coordinate[0]][coordinate[1]];
        }

        return nodes;
    }

    private int[] getNextCoordinate(int row, int col, int[] move) {
        row = (row + move[0] + board.length) % board.length;
        col = (col + move[1] + board[0].length) % board[0].length;
        return new int[]{row, col};
    }

    private void go(Node startNode) {
        for (int directionIdx = 0; directionIdx < MOVES.length; directionIdx++) {
            int distance = 0;
            node = startNode;
            outputDirectionIndex = directionIdx;
            while (node != null) {
                distance += goNextNode();
            }
            if (distance > 0) {
                result.add(distance);
            }
        }

    }

    private int goNextNode() {
        if (!node.hasNewRoute(outputDirectionIndex)) {
            node = null;
            outputDirectionIndex = -1;
            return 0;
        }

        node.outputs[outputDirectionIndex]++;
        node = node.getNextNode(outputDirectionIndex);
        int offset = node.direction == 'L' ? 1
                : node.direction == 'R' ? 3
                : 2;
        outputDirectionIndex = (outputDirectionIndex + offset + 2) % 4;

        return 1;
    }

    private static class Node {
        public char direction;
        public int[] outputs;
        public Node[] nextNodes = new Node[4];

        public Node(char direction, int[] outputs) {
            this.direction = direction;
            this.outputs = outputs;
        }

        public boolean hasNewRoute(int outputDirectionIdx) {
            return outputs[outputDirectionIdx] == 0;
        }

        public Node getNextNode(int outputDirectionIdx) {
            return nextNodes[outputDirectionIdx];
        }

    }
}