(프로그래머스 JS)빛의 경로 사이클

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

코딩테스트 연습 - 빛의 경로 사이클

BFS 알고리즘.

 

처음 풀 때는 DFS를 사용했지만, 런타임 에러 즉, 콜스택이 초과되기 때문에 BFS를 사용해야 한다.

각 좌표마다 시작하는 방향에 따라 사이클의 여부가 달라지기 때문에, 3차원 배열을 이용해 visited를 처리했다.

 

우선 이중 for문으로 grid를 순회한다.

순회를 하면서 각 좌표마다 4방향으로 탐색을 진행한다.

단, 탐색 시작의 조건은 이전에 방문한 적이 없을 경우다.

방문한 적이 있다면 같은 계산을 반복하기 때문에 가지를 쳐서 수행 횟수를 줄이는 것이다.

 

bfs()함수와 go() 함수를 정의해 구현.

bfs에는 시작 좌표와 시작 방향을 넘겨주도록 한다.

그러면 bfs 안에서 go 함수를 이용해 탐색을 한다.

 

go() 함수는 인자로 받아온 좌표에서 빛의 다음 방향과 좌표를 결정해준다.

switch를 이용해 grid[x][y]에 따라서 좌표를 설정해 주었다.

또한, to 는 변수로 S, L, R에 따라 빛을 꺽거나 직진시키도록 한다.

 

go의 리턴값은 다음 방문할 좌표이므로, queue에 넣어서 bfs를 진행.

만약 queue에서 꺼낸 좌표값을 방문한 적이 있다면 answer에 len push.

 

정답 리턴 값은 answer을 오름차순으로 정렬한다.

function solution(grid) {
    const answer = [];
    const m = grid.length;
    const n = grid[0].length;
    const direct = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = Array.from({length: m}, () => Array.from({length: n}, () => Array(4).fill(false)));
        
    const go = (x, y, from) => {
        let nx = x;
        let ny = y;
        let to = from;
        
        switch(grid[x][y]){
            case "S":
                if(from === 0){
                    nx--;
                } else if(from === 1){
                    nx++;
                } else if(from === 2){
                    ny--;
                } else if(from === 3){
                    ny++;
                }
                break;
            case "L":
                if(from === 0){
                    ny--;
                    to = 2;
                } else if(from === 1){
                    ny++;
                    to = 3;
                } else if(from === 2){
                    nx++;
                    to = 1;
                } else if(from === 3){
                    nx--;
                    to = 0;
                }
                break;
            case "R":
                if(from === 0){
                    ny++;
                    to = 3;
                } else if(from === 1){
                    ny--;
                    to = 2;
                } else if(from === 2){
                    nx--;
                    to = 0;
                } else if(from === 3){
                    nx++;
                    to = 1;
                }
                break;
        }
        
        nx = nx < 0 ? m - 1 : nx === m ? 0 : nx;
        ny = ny < 0 ? n - 1 : ny === n ? 0 : ny;
        
        return [nx, ny, to];
    }
    
    const bfs = (x, y, d) => {
        const queue = [[x, y, d, 0]];
        
        while(queue.length){
            const [cx, cy, cd, len] = queue.shift();
            const [nx, ny, nd] = go(cx, cy, cd);
            
            if(visited[cx][cy][cd]){
                answer.push(len);
                
                return;
            }
            
            visited[cx][cy][cd] = true;
            queue.push([nx, ny, nd, len + 1]);
        }
    }
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            for(let k = 0; k < 4; k++){
                if(!visited[i][j][k]){
                    bfs(i, j, k);
                }
            }
        }
    }
    
    return answer.sort((a, b) => a - b);
}