[프로그래머스][LEVEL2] 빛의 경로 사이클

# 문제 원문

 

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

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 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]

 

# 문제 풀이

 

어렵다. 2레벱이 특정 알고리즘 기본 수준의 문제이고 3레벨이 2레벨의 응용이라는 설명대로라면 이건 2레벨 보다는 3레벨에 가까운 문제이다. 머릿속에 빛의 경로 사이클을 직접 그려낼 수 있냐 없냐에 따라서 난이도가 달라질 것이라 보인다. 3차원 배열을 만들어 내고 그것을 탐색 하는 것 까지는 크게 어렵지 않았지만 빛의 방향에 대한 로직이 헷갈려서(머릿속에 선명히 그려지질 않더라) 팁을 보고 풀었다. 기하에 대해서 별로 익숙하지 않은 점이 여기서 걸리는거 같다. 내 약점으로 머릿속의 도형의 움직임 같은 것을 생각하기 어려워 한다는 점을 느꼈다. 추가로 탐색 시작 방향은 완전 탐색후 반환값을 오름차순 정렬하기에 신경쓸 필요가 없다.

 

# 솔루션 플로우

1. 입력 받은 grid의 각 격자의 상하좌우 4방향을 표현한 3차원 배열 cycle을 얻는다.

2. 빛의 방향 down, right, up, left의 좌표 변화 값 direct를 얻는다.

3. cycle의 각 격자의 4가지 방향을 탐색하면서 방문하지 않은 방향부터 탐색을 시작한다.

4. 현 지점 부터 이미 방문한 지점을 만나기 전까지 방문한 지점들을 체크하면서 탐색을 시작한다. (현재 지점과 방향)

5. 방문하는 격자에 따라서 방향을 변경해가며 방문한 route를 모두 카운팅하여 구한다.

6. 입력 받은 grid의 모든 루트를 방문해서 얻은 result를 오름차순 정렬한다.

7. result를 반환한다.

1. 완전탐색 & 반복문을 활용한 풀이

function solution(grid) {
    const result = [];
    const cycle = grid.map((row) => row.split('')
        .map((_) => new Array(4).fill(true)));
    const direct = [[1, 0], [0, 1], [-1, 0], [0, -1]];

    cycle.forEach((row, rdx) => {
        row.forEach((col, cdx) => {
            col.forEach((route, idx) => {
                if (route) {
                    result.push(checkCycle(rdx, cdx, idx))
                }
            });
        });
    });


    function checkCycle(rdx, cdx, idx) {
        let result = 0;

        while (true) {
            if (!cycle[rdx][cdx][idx]) break;
            cycle[rdx][cdx][idx] = false;
            result++;

            rdx += direct[idx][0];
            cdx += direct[idx][1];
            if (rdx < 0) rdx = cycle.length - 1;
            if (rdx >= cycle.length) rdx = 0;
            if (cdx < 0) cdx = cycle[0].length - 1;
            if (cdx >= cycle[0].length) cdx = 0;

            if (grid[rdx][cdx] === "L") idx = [1, 2, 3, 0][idx];
            if (grid[rdx][cdx] === "R") idx = [3, 0, 1, 2][idx];
        }

        return result;
    }

    return result.sort((a, b) => a - b);
}