[JS] 빛의 경로 사이클

진짜 레벨 2중에 가장 어려운 것 같아요. 체감상...

그냥 상하좌우로 경로따라가다가 그냥 머리까지 돌아가버림ㄹㅇ

거의 하루종일 이거만 했네요. 다들 잘 푸셨나요?

같이 한번 찬찬히 살펴봐요!

 

---

문제 요약

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

그냥 보기부터 싫어지는 그래프

• 이 노드들로 들어오는 빛의 방향에 따라 거울처럼 반사됩니다.
  왼쪽에서 빛을 쐈을 때 각각 이런 식으로 동작합니다.
  • S 노드: 그대로 통과시키고, col을 1 늘려줍니다.
  • L 노드: 왼쪽으로 들어온 빛 기준으로 좌회전합니다. 그래서 위쪽으로 갑니다. row를 1빼줍니다.
  • R 노드: 왼쪽으로 들어온 빛 기준으로 우회전합니다. 그래서 아래쪽으로 갑니다. row를 1 더해줍니다.

결국 계속 반사되면서 처음 위치로 처음 빛 방향대로 온다면 사이클을 형성한 것으로 간주합니다.

빛의 경로 사이클의 모든 길이를 담은 배열을 결과로 내주면 됩니다.

 

문제 해석

원래 이런 그래프 이동 문제는 보통 dx, dy를 정하고 재귀함수로 순회하는 관성적인 습관이 있는데요.

그렇게 돌려버리면 이제 메모리 스택을 그냥 넘습니다.

 

전 두번째로는 해시맵을 써봤었는데요. L노드의 반사 해시맵 (ex. LMap.set("l", "u") 뭐.. 이런 느낌), R 노드의 반사 해시맵 등을 정의하고 거기에 반사된 방향으로 단위 거리를 더해줘봤는데...... 일단 시간 초과더라구요. 이것도 기각!

 

결론적으로는 3중 루프를 돌릴 수 밖에 없습니다.

각 노드 별로 나가는 방향을 담은 배열로요. 저는 visited를 선언했고, 각 요소는 visited[row][col][direction] 이렇게 정의했습니다.

 

자 코드 보시죠!

 

정답 코드

function solution(grid) {
    const [maxRow, maxCol] = [grid.length, grid[0].length];
    const visited = Array.from({length: maxRow}, () => Array.from({length: maxCol}, () => [false, false, false, false]));
    // [l, u, r, d];
    // L: l => d, r => u, u => l, d => r
    // R: l => u, r => d, u => r, d => l
    const lTable = [3, 0, 1, 2];
    const rTable = [1, 2, 3, 0];
    const dx = [-1, 0, 1, 0];
    const dy = [0, -1, 0, 1];
    const result = [];
    for (let i = 0; i < maxRow; i++) {
        for (let j = 0; j < maxCol; j++) {
            for (let k = 0; k < 4; k++) {
                if (visited[i][j][k]) continue;
                let [row, col, dir] = [i, j, k];
                let count = 0;
                while (!visited[row][col][dir]) {
                    visited[row][col][dir] = true;
                    if (grid[row][col] === "L") {
                        dir = lTable[dir];
                    } else if(grid[row][col] === "R") {
                        dir = rTable[dir];
                    }
                    row += dx[dir];
                    col += dy[dir];
                    if (row < 0) row = maxRow - 1;
                    else if (row === maxRow) row = 0;
                    if (col < 0) col = maxCol - 1;
                    else if (col === maxCol) col = 0;
                    count++;
                }
                result.push(count);
            }
        }
    }
    return result.sort((a, b) => a - b);
}

 

노드에 반사되는 빛을 저는 lTable, rTable로 정의하고 노드의 값을 비교해서 사용해줬습니다.

주석을 해뒀지만 이걸 이해하는게 중요해요.

	// [l, u, r, d];
    // L: l => d, u => l, r => u, d => r
    // R: l => u, u => r, r => d, d => l
    const lTable = [3, 0, 1, 2];
    const rTable = [1, 2, 3, 0];

index 별로 저는 left, up, right, down으로 저만의 정의를 했습니다.

만약 L 노드를 만났을 때 어떻게 변화할지 생각해줍시다.

여기에서 중요한건, 빛의 나가는 방향을 기준으로 할지, 들어오는 방향을 기준으로 할지를 헷갈리지 마셔야한다는 점입니다. (전 나가는 방향을 기준으로 했습니다.)

1. 만약 이전 노드에서 왼쪽으로 빛이 반사시켰고, 이게 L 노드에 도착했습니다.
2. L노드 기준으론 오른쪽에서 빛이 도착했습니다. 따라서 아래쪽으로 반사시켜줍니다.

예....

이런 원리로 테이블을 어떻게 바꿀지 하나하나 생각하셔서 적어주시면 됩니다.

 

그 다음은 3중 loop안에 있는 while문에 대해서 동작원리를 살펴보면 크게 어려운 부분은 없을 거에요.

while (!visited[row][col][dir]) {
    visited[row][col][dir] = true; //일단 노드 도착했으니 true로 바꿔줍니다.
    if (grid[row][col] === "L") {
        dir = lTable[dir];
    } else if(grid[row][col] === "R") {
        dir = rTable[dir];
    }//아까 실컷 말한 노드에 따른 방향 shift입니다. S는 그냥 그대로 내보내시면 돼요.
    row += dx[dir];
    col += dy[dir];//단위 벡터를 더해주고 범위넘어간 거만 약간 조정해줍시다.
    if (row < 0) row = maxRow - 1;
    else if (row === maxRow) row = 0;
    if (col < 0) col = maxCol - 1;
    else if (col === maxCol) col = 0;
    count++;
}

이렇게 해두면 이제..

알아서 한 사이클을 찾아서 돌 수 있습니다.

그리고 visited가 true면 바로 다음 루프로 넘어가는 continue 로직을 넣어서 낭비를 최대한 줄여줍시다!

 

정말 어렵네요..

레벨 2중에 가장 어려웠어요...

겸손 또 겸손해집니다.

 

그럼 이만!