각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.
예를 들어, 다음 그림은 격자 ["SL","LR"]
에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.
이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.
격자의 정보를 나타내는 1차원 문자열 배열 grid
가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.
grid
의 길이 ≤ 500
grid
의 각 문자열의 길이 ≤ 500grid
의 모든 문자열의 길이는 서로 같습니다.grid
의 모든 문자열은 'L', 'R', 'S'
로 이루어져 있습니다.grid | result |
---|---|
["SL","LR"] |
[16] |
["S"] |
[1,1,1,1] |
["R","R"] |
[4,4] |
입출력 예 #1
[16]
을 return 해야 합니다.입출력 예 #2
[1,1,1,1]
을 return 해야 합니다.입출력 예 #3
[4,4]
를 return 해야 합니다.출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
이번 문제는 우선 배열을 아래와 같이 정의한다.
[x,y,방향]
여기서 방향은 내가 어디로 움직있는지 상하좌우
인덱스 0 => 우, 1 => 상, 2=> 좌 3 => 하 로 정의
- 여기서 추가적으로 보면 좌회전 하면 저 인덱스를 +1로 바꿔주면 된다.
원래는 우측으로 가고 있는데 좌회전이라면 인덱스 +1 에 해당하는 상이 된다.
우회전에 경우는 -1을 해주면 된다.- 위의 찾은 규칙을 통해서 아래와 같이 규현
- coorFun(좌표) 함수 생성 => 이 함수는 현재 좌표를 넣어주면 방향을 알아서 틀어줌과 통시에 그 뱡향으로 한칸 이동한 좌표를 리턴하는 함수이다.
- visitArr 생성
=> 이는 3차원 배열로 x,y,방향으로 3차원으로 만들어주면서 기본값은 false로 해준다. (true라면 방문한것으로 정의)- 이제 순환을 해줄껀데 총 3중 for문을 써야한다.
-> x,y,방향 => ex) 2,3,1 => x=2,y=3,방향=오른쪽으로 움직임.
3중 for문의 값을 var current = [dx,dy,dirIndex] 로 받고 아래 과정 시행
1) 만약 그 값이 visitArr에 true라면 pass -> 건너뜀
2) 아니라면 방문한 것을 만날때까지 아래 반복
우선 그 x,y,방향에 해당하는 visitArr에 값을 true로 바꾼다.
그 값을 plusArr 에 따로 모아둔다.
그 후에, 위에 만든 함수를 이용하여 좌표를 이동한다.
3) 이렇게 해서 나온 plusArr의 length를 answer에 추가해준다.- 마지막에는 answer을 오름차순 정렬해서 리턴한다.
function solution(grid) {
var answer = [];
//0 => 우측으로 이동, 1=>위로 이동, 2=> 좌측으르 이동, 3=> 아래로 이동
var dirIndex = 0;
grid = grid.map((element)=>{
return element.split("");
})
var xLen = grid[0].length;
var yLen = grid.length;
//함수에 현재 위치 좌표를 주면 그 다음 좌표를 리턴
// 방향을 틀고 글로 이동한다.
// ex) current = [0,0]
function coorFun(current){
// 방향을 트는 과정
if(grid[current[1]][current[0]]==="S"){
}
else if(grid[current[1]][current[0]]==="L"){
// L에 걸리면 index 를 +1 해준다. 단, 3을 넘어가면 0으로 초기화
dirIndex = dirIndex>=3? 0:dirIndex+1;
current[2] = dirIndex;
}
else if(grid[current[1]][current[0]]==="R"){
dirIndex = dirIndex<=0? 3:dirIndex-1;
current[2] = dirIndex;
}
// dirIndex ===0 => 우측으로 이동
if(dirIndex === 0){
//x좌표에 1 증가
current[0] = current[0] >= xLen -1 ? 0 : current[0]+1;
}
// 위로 이동
else if(dirIndex===1){
current[1] = current[1] >= yLen -1 ? 0 : current[1]+1;
}
// 좌측으로 이동
else if(dirIndex===2){
//x좌표에 1 감소
current[0] = current[0] <=0 ? xLen - 1 : current[0]-1;
}
// 아래로 이동
else if(dirIndex===3){
//y좌표에 1 감소
current[1] = current[1] <=0 ? yLen - 1 : current[1]-1;
}
return current;
}
var visitArr = Array.from(Array(yLen), () => Array.from(Array(xLen), () => Array(4).fill(false)));
for(var dx = 0; dx<xLen;dx++){
for(var dy = 0; dy<yLen;dy++){
for(var i =0;i<4;i++){
dirIndex = i;
var plusArr = [];
// 0,0, 방향
var current = [dx,dy,dirIndex];
if(visitArr[current[1]][current[0]][current[2]]){
continue;
}
while(!visitArr[current[1]][current[0]][current[2]]){
visitArr[current[1]][current[0]][current[2]] = true;
plusArr.push([...current]);
current = coorFun([...current]);
}
plusArr.forEach((element)=>{
visitArr[element[1]][element[0]][element[2]] = true;
})
answer.push(plusArr.length);
}
}
}
return answer.sort((a,b)=>a-b);
}