[프로그래머스] 빛의 경로 사이클 / Javascript
문제주소 :https://programmers.co.kr/learn/courses/30/lessons/86052#
코딩테스트 연습 - 빛의 경로 사이클
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진
programmers.co.kr
<문제 설명>
문제 설명
각 칸마다 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'로 이루어져 있습니다.
입출력 예
gridresult| ["SL","LR"] | [16] |
| ["S"] | [1,1,1,1] |
| ["R","R"] | [4,4] |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
- 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.
입출력 예 #2
- 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.
- 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.
입출력 예 #3
- 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.
- 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.
<풀이법>
▒ 한줄 개념: 완전탐색 ▒
완전탐색을 구현해야하는 문제입니다.
각 칸은 4방향으로 들어오는 routes를 가지고 있으므로, 3차원의 routes 배열을 visited의 개념으로 사용하여 구현해주었습니다.
또한, 문제에 S, R, L 뿐이 없다는 뜻은, 뒤로 돌아가는 칸이 없다는 뜻이므로, 이는 사이클이 최소한 하나는 무조건 생긴다는 뜻이 됩니다. 다시 말해, 어떤 routes에서 빛을 쏘던 해당 routes로 돌아오는 것은 필연적이기 때문에, 이를 염두하며 완전탐색을 구현하면 문제를 풀 수 있습니다.
우선 구현을 떠나서, 제가 고생했던 2가지 포인트에 대해 공유하고자 합니다.
1. 사이클의 올바르지 못한 이해
-> 처음 생각했던 사이클은, 모든 칸을 지나서 원래 방향으로 다시 들어오는 사이클이었습니다. 비슷한 타입의 문제들 같은 경우 사이클이라 함은 항상 모든 칸을 지나는 경향이 있었던 것 같아서, 해당 방식으로 처음에 구현하였는데, 이 문제는 그런 뜻이 아니었습니다. 이 문제에서는 모든 칸을 다 지나가지 않더라도 처음 routes로 돌아오게 되면, 사이클이 됩니다.
2. javscript에서 dfs 사용시 런타임 에러
-> 처음에 dfs로 구현하였었는데, 중간 테스트 케이스들에서 런타임 에러가 발생하는 것을 확인할 수 있었습니다. 결론부터 말하자면, javascript의 경우 dfs로 완전탐색을 구현하면 콜 스택 초과가 발생하는 것 같습니다. 이전에 다른 문제에서도 파이썬을 사용하여 dfs를 구현하였다가 똑같은 경험을 했던 적이 있어서, 혹시나 해서 동일한 로직을 bfs로 구현하였더니 런타임 에러가 발생하지 않았습니다.
javascript와 dfs를 사용하여 구현하신다면, dfs 탐색 조건을 더 까다롭게 하여 콜 스택 참조를 줄이거나, 아예 bfs로 구현해야 문제를 해결할 수 있으리라 생각됩니다. 저는 결국 bfs를 선택했습니다..
다시 돌아가 풀이과정을 순서대로 표현하면, 다음과 같습니다.
1. routes 초기화(3차원 배열 초기화)
2. 모든 routes에 대하여 완전 탐색 진행(bfs/dfs)
2-1. 이미 탐색된(방문된) routes에 대해서는 탐색을 진행하지 않음
2-2. 처음 탐색했던(방문했던) routes에 도달하게 되면, 이동한 길이(사이클의 길이)를 answer에 삽입
3. answer를 오름차순으로 정렬한 뒤 return
<코드(Javascript)>
function solution(grid) {
const answer = [];
const [N, M] = [grid.length, grid[0].length];
const routes = {};
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) => {
const queue = [[startR, startC, startDir, 0]];
while (true) {
let [r, c, dir, len] = queue.pop(0);
r = r === N ? 0 : r === -1 ? N-1 : r;
c = c === M ? 0 : c === -1 ? M-1 : c;
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;
}
}
}
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));
}
})
}
}
answer.sort((a, b) => a - b);
return answer;
}
더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest