빛의 경로 사이클

https://school.programmers.co.kr/learn/courses/30/lessons/86052?language=javascript

프로그래머스

• 사이클의 존재 유무와 그것의 길이는 이미 지나쳤던 경로를 한 번 더 지나는지를 판별하면 알 수 있음.
• 처음에 해맸던 점은 이것을 0,0 지점에 위치한 노드만 봐야하는지와 모든 지점을 거쳐야지만 사이클이 되는지였다.
• 결과적으로 한 지점에서 출발하여 모든 지점을 지나칠 필요는 없으며, (0,0)이 아니더라도 사이클을 찾으면 되느 것이었다.
• 즉, 반복문을 통하여 (0,0)~(n-1,m-1) 까지 모든 점을 돌아다니면서 사이클을 찾으면 됨
• 이때 방문 그래프 visited를 선언할 것인데 한 번 지나쳤던 경로라면 위에서 언급했던 모든 점을 돌아댕길 때 또 탐색 할 필요는 없음 ( 사이클이 있든 없든 이전에 탐색했던 경로라면 결과는 같으니까)
• 또한, 한 지점에서 나아갈 수 있는 방향은 4방향이므로 visited는 [i][j][4] 가 된다. 

const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => [-1, -1, -1, -1])
);

• 이후에는 탐색을 통해서 left,right 에 대한 방향과 범위를 넘어섰을 때의 좌표값만 유의하면 어려운 점은 없음
•  

const dy = [0, 1, 0, -1];
const dx = [1, 0, -1, 0];
// Right,Down,Left,UP
// "L" : -1
// "R": +1

const bfs = (ia, visited, grid, sx, sy) => {
    const n = grid.length;
    const m = grid[0].length;
    visited[sx][sy][ia] = 0;

    const q = [[sx, sy, ia]];
    while (q.length) {
        const [x, y, dir] = q.shift();
        let nextDir = dir;
        if (grid[x][y] === 'R') nextDir = (nextDir + 1) % 4;

        if (grid[x][y] === 'L') nextDir = (nextDir + 3) % 4;

        let nx = x + dx[nextDir];
        let ny = y + dy[nextDir];
        if (nx < 0) nx = n - 1;
        if (ny < 0) ny = m - 1;
        if (nx >= n) nx = 0;
        if (ny >= m) ny = 0;
        if (visited[nx][ny][nextDir] !== -1) return visited[x][y][dir] + 1;
        visited[nx][ny][nextDir] = visited[x][y][dir] + 1;
        q.push([nx, ny, nextDir]);
    }
    return false;
};

function solution(grid) {
    const answer = [];

    const n = grid.length;
    const m = grid[0].length;

    const gr = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => [-1, -1, -1, -1])
    );
    for (let x = 0; x < n; x++) {
        for (let y = 0; y < m; y++) {
            for (let i = 0; i < 4; i++) {
                if (gr[x][y][i] !== -1) continue;
                const result = bfs(i, gr, grid, x, y);
                if (result !== false) {
                    answer.push(result);
                }
            }
        }
    }

    return answer.sort((a, b) => a - b);	// sort 안해줘서 계속 틀렸음
}