[JS] 빛의 경로 사이클

🔒 문제 (프로그래머스 월간 코드 챌린지 시즌3)

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

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

---

제한사항

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

 

🌊 입출력

grid	result
["SL","LR"]	[16]
["S"]	[1,1,1,1]
["R","R"]	[4,4]

 

---

 

🔑 해결

🌌 알고리즘 - BFS

1) 사이클의 특성 상 시작 지점과 상관 없이 이동 경로가 하나라도 겹친다면 같은 사이클이 된다

=> 한번 방문했던 노드는 다시 탐색할 필요 x

또한 모든 칸을 지나가지 않아도 처음 경로로 돌아오면 사이클이 됨

2) 같은 위치에서 빛이 상, 하, 좌, 우 4방향에서 들어오는 경우가 모두 다른 경로를 만들게 된다

=> x,y 좌표와 빛이 들어오는 방향 3가지를 모두 고려하여 방문여부를 체크하기 위해 3차원 visited 배열 필요

따라서 BFS로 모든 노드를 방문하며 사이클을 찾는다 (DFS는 런타임 에러)

노드가 저장할 정보: [x좌표, y좌표, 현재 격자로 빛이 들어오는 방향, 사이클 길이] = [r, c, dir, len]

 

한 격자에 대하여 빛의 방향을 정리하면 아래와 같고

L격자를 예시로 각 방향에서 빛이 들어온 경우를 표현하면 아래와 같다

 

 

function solution(grid) {
    let answer = [];
    const [N, M] = [grid.length, grid[0].length];
    const routes = [];  // 3차원 visited 배열 역할
    for(let r = 0; r < N; r++) {
        routes[r] = [];
        for(let c = 0; c < M; c++) {
            routes[r][c] = {
                u: 0,
                d: 0,
                l: 0,
                r: 0,
            };
        }
    }
    
    const bfs = (startR, startC, startDir) => {
        // (startR, startC): 현재 위치, startDir: 빛이 들어오는 방향 
        const queue = [[startR, startC, startDir, 0]];
        
        while(true) {
            let [r, c, dir, len] = queue.pop();
            
            // 빛이 격자의 끝을 넘어갈 경우 index 재설정
            r = r === N ? 0 : r === -1 ? N-1 : r;
            c = c === M ? 0 : c === -1 ? M-1 : c;
            
            // 이미 방문한 node를 만난 경우 사이클의 끝이므로 길이 반환
            if(r === startR && c === startC && dir === startDir && len) {
                return len;
            }
            
            routes[r][c][dir] = 1;  // 방문 여부 저장
            switch(grid[r][c]) {
                case 'S':
                    queue.push(
                        dir === 'u' ? [r + 1, c, 'u', len + 1]
                        : dir === 'd' ? [r - 1, c, 'd', len + 1]
                        : dir === 'l' ? [r, c + 1, 'l', len + 1]
                        : [r, c - 1, 'r', len + 1]
                    );
                    break;
                case 'L':
                    queue.push(
                        dir === 'u' ? [r, c + 1, 'l', len + 1]
                        : dir === 'd' ? [r, c - 1, 'r', len + 1]
                        : dir === 'l' ? [r - 1, c, 'd', len + 1]
                        : [r + 1, c, 'u', len + 1]
                    );
                    break;
                case 'R':
                    queue.push(
                        dir === 'u' ? [r, c - 1, 'r', len + 1]
                        : dir === 'd' ? [r, c + 1, 'l', len + 1]
                        : dir === 'l' ? [r + 1, c, 'u', len + 1]
                        : [r - 1, c, 'd', len + 1]
                    );
                    break;
            }
        }
    }
    
    // 하나의 노드는 4방향에서 빛을 받을 수 있음
    const directions = ['u', 'd', 'l', 'r'];
    for(let r = 0; r < N; r++) {
        for(let c = 0; c < M; c++) {
            directions.map(dir => {
                // 방문하지 않은 모든 노드에 대하여 사이클 찾기
                if(!routes[r][c][dir]) {
                    answer.push(bfs(r, c, dir));
                }
            })
        }
    }
    
    return answer.sort((a, b) => a - b);
}

 

 

 

참고 https://dev-note-97.tistory.com/302