[JS] 빛의 경로 사이클

개인적으로 이런 2차원 배열 관련 문제들을 좋아해서 재밌었던 문제였다. 문제의 핵심은 한번 빛이 지나간 경로를 따라가면 한 사이클이 된다는 것이다.

 

visited배열을 통해서 Node의 방문 기록을 저장해줘야 하는데 Node당 4방향으로 빛이 나갈 수 있기 때문에 각 방향마다 방문을 기록할 수 있도록 저장해두었다.

즉 , NODE마다 [false,false,false,false,"S"] 이런식으로 각 노드의 정보와 방문기록을 저장해두었다.

 

필자는 dx,dy 배열을 우-하-좌-상 방향으로 저장해두었다.

 

이렇게 저장한 이유는 우측으로 회전하는 순서대로 저장해두어 dx에 1씩더하면 우회전, 1씩 빼면 좌회전이 되기 때문이다.

 

 

JS에선 -1을 두어도 역순으로 가지 않기 때문에 makeRange함수로 0~n이넘어가도 해당 안의 값으로 만들어주는 함수를 선언해서 사용했다.

 

 

이어서 진행하는 과정은 다음과 같다.

 

1. 한번도 지나가지 않은 방향의 NODE면 개수를 세기 시작

2. 스택을 활용해서 지나갈 곳이 처음 방문한 곳이라면 계속 카운트

3. 지나간 곳이 나온다면 사이클이 끝난 것이므로 ret에 cnt값을 저장하고 방문하지 않은 다음 노드로 탐색

4. 최종적으로 ret를 오름차순하고 마무리

 

 

 

 

function solution(grid) {
    const dx = [1,0,-1,0]
    const dy = [0,1,0,-1] // dx,dy를 둬서 방향을 둘 수 있게
    
    
    const visited = [... new Array(grid.length)].map((_,i) => grid[i].split("").map(el => [...new Array(4).fill(false),el]))
    //visited배열을 둬서 해당노드에서 배열이 4방향으로 쏜 기록을 저장
    
    const ret = [] //횟수를 저장할 배열
    
    const makeRange = (num,range) => {
        if (num < 0) return range + num
        return num%range
    } // 0~n사이로 값을 고정하게 만들어주는 함수
    
    const colLen = visited.length
    const rowLen = visited[0].length
	//세로,가로줄 크기
    
    for (let i = 0 ; i < colLen ; i++) {
        for (let j = 0; j < rowLen ; j++) {
            for (let k = 0 ; k <4 ; k++) {
                if (visited[i][j][k]) continue //지나갔던곳이면 pass
                
                visited[i][j][k] = true
                const nx = makeRange(j + dx[k],rowLen)
                const ny = makeRange(i + dy[k],colLen)
                //다음 지나갈 곳을 설정
                const stk = [[ny,nx,k]]
                let cnt = 1
                while (stk.length) {
                    let [y,x,d] = stk.pop()
                    const state = visited[y][x][4]
                    // 왼쪽 회전이면 dx,dy배열에서 각각 -1, R이면 1씩 더한것과 같음
                    if (state==="L") d = makeRange(d-1,4)
                    else if (state==="R") d = makeRange(d+1,4)
                    if (visited[y][x][d]) continue
                    visited[y][x][d] = true
                    const nx = makeRange(x + dx[d],rowLen)
                    const ny = makeRange(y + dy[d],colLen)
                    stk.push([ny,nx,d])
                    cnt ++
                }
                ret.push(cnt)
            }
        }
    }
    
    
    return ret.sort((a,b) => a-b)
}