프로그래머스_JS - 빛의 경로

nd098pkc·2022년 7월 13일
0

코딩테스트 준비

목록 보기
15/15

프로그래머스 월간 코드 챌린지 시즌 3에서 레벨 2로 분류된 문제입니다.
월간 코드 챌린지 시즌3에는 어떤 일이 있었던걸까요..

문제

솔직히 레벨2 치고 난이도가 어려웠다고 생각합니다. 어렵다기보다 머리속에 떠오른 방법이 모든 경우의 수에 해당되는지 확신하기가 힘들었던 문제라고 표현하는게 정확할 수도 있겠네요.

풀이과정

<입력>

  1. 빛이 통과하는 격자의 정보를 나타내는 배열 "grid"(Array)

<모든 사이클 경로를 탐색했다는 확신>

빛을 한 방향으로 쏴줬을 때 규칙에 따라 이동시키는 것은 어렵지 않았습니다. 하지만 모든 사이클을 다 탐색했는지 확신하는 것, 그리고 지금 돌고 있는 사이클이 예전에 탐색했던 사이클과 중복되지 않는다는 것을 어떻게 체크해야 하는지 그부분이 생각해내기 쉽지 않았고 결국 완전탐색으로 접근해보기로 했습니다.

<사이클의 정보 저장>

격자의 형태가 어떻든간에 한 격자에서 빛이 나간 방향은 사이클간에 중복이 불가능합니다. 이것이 무슨말이냐 하면 [0,0]격자에서 오른쪽으로 출발한 빛의 사이클을 A라고 할 때 [0,0]에서 오른쪽으로 향하는 빛은 무조건 A사이클에 밖에 존재하지 않는다는 뜻입니다. 따라서 visited라는 배열을 만들어 빛이 이동할때마다 각 격자에서 빛을 내보내는 방향을 저장해두면 다음번에 빛이 이동할때 같은 방향으로 이동하려한다면 중복되는 사이클이라는 것을 알 수 있을것입니다. 또한 visited에서 모든 격자에서 위,아래, 왼쪽, 오른쪽 모든 방향으로 빛이 이동한 정보가 있다면 모든 사이클을 탐색했다고 확신하는데 활용 할수도 있을것입니다.

let visited = Array.from({length:grid.length},()=>Array.from({length:grid[0].length},()=>[]))
// 복잡하지만 3차원배열 구현. 각 격자별로 나간 방향을 저장해 줄 것입니다.

let paths=[]  // 각 경로 저장해줄 배열
let directions = ['d','l','u','r']  // 빛이 이동 가능한 네 방향을 미리 저장. 

let count=0                                   //경로의 갯수
    for(let i=0; i<visited.length;i++){       
        for(let j=0;j<visited[0].length;j++){ // 0,0격자부터 각 격자를 순회
            for(let k=0;k<4;k++){             // 모든 방향을 체크하면서
                if(!visited[i][j].includes(directions[k])){ //해당 격자에서 가보지 않은 방향이 있으면
                   paths[count]=[]            // 사이클 경로를 넣어줄 배열을 초기화해주고 
                    findPath(count,k,i,j)     // 나중에 구현해줄 함수를 통해 사이클을 추가.
                    count++                   
                }
            }
        }
    }

일단 큰 틀은 완성했습니다. 각 격자별로 네 방향을 모두 체크하면서 진행했기 때문에 누락된 사이클 없이 모든 사이클을 탐색할 수 있고, 격자에 대해 확인할 때 이전 사이클에서 이동해본 적 없는 방향(if(!visited[i][j].includes(directions[k])))만 탐색했기 때문에 중복된 사이클도 없는 완전탐색 로직이라고 볼 수 있습니다.
그렇다면 이제 빛을 이동시켜가면서 격자에서 나간 방향을 visited에 저장해주고 경로는 paths에 저장해주면 되겠네요!

<빛 객체와 경로탐색 함수>

하지만 그 전에 빛 경로 계산을 용이하게 해줄 친구를 미리 만들어두고 시작하려고합니다.
격자의 종류에 따라 빛이 들어오는 방향이 다르게 나가기 때문에 그 경우의수를 모두 조건문으로 처리하면 복잡해보일것 같기도 하고, 빛의 이동을 생각하는데 조금 더 직관적으로 계산할 수 있을것 같았기 때문입니다.

class Light{
    constructor(x,y,dir){    //제일 처음 빛의 위치와 이동 방향 지정 가능
        this.x = x;
        this.y = y;
        this.direction = dir     //'d', 'u', 'l', 'r'중 하나
    }
    move(h, w){              // direction에 따른 빛의 이동, h=x최대값(격자의 높이), w=y최대값(격자의 너비)
        switch(this.direction){
            case 'd' :       //밑으로 = x가 1 증가, x 최대값보다 커질수 있으므로 %연산하여 할당
                this.x = (this.x+1)%h
                break;        
            case 'u' :       //위로 = x가 1 감소, 0보다 작아질 수 있으므로 h를 더한 후 %연산하여 할당
                this.x = (this.x -1 + h)%h
                break;
            case 'l' :       //왼쪽으로 
                this.y = (this.y -1 + w)%w
                break;
            case 'r' :       //오른쪽으로
                this.y = (this.y+1)%w
                break;
        }
    }
}

이제 경로탐색 함수를 실행시킬 때 시작점과 출발시킬 방향을 지정하고 빛을 규칙에 따라 이동시켜주면 되겠습니다.

function findPath(idx,firstdir,startx,starty){ // (몇번째경로인가, 시작방향, 시작x좌표, 시작y좌표)
    let diridx = firstdir
    let light = new Light(startx,starty,directions[diridx])  //시작점에 시작방향으로 세팅된 빛을 생성해줍니다.

    while(true){
    if(visited[light.x][light.y].includes(light.direction)){ 
            break;                        //현재 좌표에서 현재 지정된 방향으로 간적이 있으면 break;
        }

    paths[idx].push([light.x,light.y])               //idx번째 경로에 현재 좌표 추가
    visited[light.x][light.y].push(light.direction) //visited의 현재좌표에 지금 출발하는 방향을 기록
    light.move(grid.length,grid[0].length)        //빛 이동

    switch(grid[light.x][light.y]){               //이동한 격자의 정보에 따라 방향 변경
        case 'L':
            diridx = (diridx+3)%4;     
            //directions 배열의 순서(d->l->u->r)는 회전에 따른 변경 순서를 고려하여 
            index를 하나씩 늘리거나 줄여서 원하는 방향으로 회전할 수 있도록 배치한 순서입니다.
            light.direction=directions[diridx];
            break;
        case 'R':
            diridx = (diridx+1)%4;
            light.direction=directions[diridx];
            break;
            }
        }
    }

일단 빛 객체를 생성해두고 빛이 이동할때마다 paths에는 idx번째(반복문에서 함수 실행시킬때마다 1씩 증가해줄 변수)배열에 사이클을 저장해주고, visited에는 출발격자에서 이동한 방향을 저장해주었습니다.
한 사이클이 끝나고 나면 각 격자별로 이동한 이력이 있는 방향이 저장되어있을텐데 반복문을 실행할 때 격자에 저장된적 없는 방향을 찾으면 그방향으로 다시 findPath함수를 실행시켜주면 모든 격자에서 모든 방향으로 빠짐없이 빛을 발사해볼 수 있습니다.


주어진 예제로 한번 생각을 해보면 해당 격자는 ["R","R"], 즉 [0,0]과 [1,0]격자가 존재하는 예제입니다.

  1. [0,0]에서 아래('d') 방향으로 빛이 출발하면 paths에는 [[[0,0]]], visited에는 [[['d']],[[ ]]], 즉 0,0에서 아래방향으로 출발한 기록이 남을것입니다. 도착하는 격자는 [0,1]입니다.
  2. 위에서 온 빛이 [0,1]인 R에서 우회전하면 진행방향은 왼쪽('l')이 됩니다. 이때 path에는 [[[0,0],[0,1]]]로 [0,1]이 추가되며 visited에는 0,1격자에 l이 추가되어 [[['d']],[['l']]]가 될것입니다. 도착하는 격자는 자기자신인 [0,1]입니다.
  3. 출발: [0,1], 방향: 위('u'), 도착: [0,0], paths:[[[0,0],[0,1],[0,1]]], visited: [[['d']],[['l','u']]]
  4. 출발: [0,0], 방향: 오른쪽('r'), 도착: [0,0], paths:[[[0,0],[0,1],[0,1],[0,0]]], visited: [[['d','r']],[['l','u']]]
  5. 여기서 규칙에 의하면 다음 빛은 [0,0]에서 'd' 방향으로 이동해야합니다. 하지만 visited의 [0,0]격자에는 이미 'd'방향으로 출발한 기록이 남아있으므로 더 진행하지 않습니다.
  6. 한 사이클을 끝낸 뒤 visited([[['d','r']],[['l','u']]])를 확인해보면 [0,0]격자에서는 'u','l'방향으로의 진행이 누락되어있고 [0,1]격자에서는 'd','r'방향으로의 진행이 누락되어있으므로 반복문을 통해 해당방향으로의 진행이 기록되게 될것입니다.

남은 과정은 paths에 기록된 각 경로의 길이를 구해 오름차순으로 정렬한 뒤 return하는것뿐입니다.

return paths.map(v=>v.length-1).sort((a,b)=>a-b)

<더 나은 답을 위하여..>

지금까지의 과정으로도 모든 테스트케이스에서 통과할 수는 있었지만 몇가지 아쉬운 점이 있었습니다.
첫번째, visited에서 격자의 이동방향 내역을 탐색할때마다 includes를 실행하다보니 실행시간이 너무 느리고 비효율적인 점.
두번째, paths에 모든 경로를 다 담다보니 메모리 활용도 비효율적인 점. 따지고보면 경로의 길이만 알면 되기때문에 모든 격자를 paths에 담을 필요는 없었다는 생각이 들었습니다.

해당 문제를 해결하기 위해 다음과 같이 변경해보았습니다

  1. visited 함수에 정보를 입력하고 해당 값을 유무를 includes로 탐색하는 것이 아닌, true of false 데이터를 입력해두고 값의 유무를 index로 확인하게 변경

    let visited = Array.from({length:grid.length},()=>Array.from({length:grid[0].length},()=>[]))
    비어있는 3차원 배열에서 변경하여

    let visited = Array.from({length:grid.length},()=>Array.from({length:grid[0].length},()=>new Array(4).fill(false)))
    각 격자마다 [false,false,false,false]로 미리 채워두고 탐색한 방향의 index는 true로 변경하여두면
    다음번에 확인할때는 index로 접근하여 더 빠르게 확인이 가능합니다.

  2. paths에 경로를 일일이 넣어줄 필요 없이 임의의 counting 변수를 만들어 격자를 방문할때 마다 늘려주도록 변경

    let paths=[] => let temp=0, let answer=[] // 경로 counting 변수와 정답을 답을 배열을 생성
    paths.push(light.x,light.y) => temp++ ,answer.push(answer) //paths에 경로를 일일이 담는 대신 counting 변수만 늘려주고 사이클이 끝나면 정답배열에 push
    return paths.map(v=>v.length-1).sort((a,b)=>a-b)=> return answer.sort((a,b)=>a-b) //return도 더 간단하게 처리 가능

수정해준 결과는?

이전과 비교했을 때 메모리와 수행속도 둘다 큰 개선이 있었습니다.

<마무리>

모든 테스트케이스를 통과한것에 만족하지 않고 더 나은 해결방법을 위해 고민한 것, 그리고 그 결과 유의미한 개선을 이뤘다는 점에서 재미있고 유익한 시간이었습니다.
앞으로도 모든 테스트케이스를 통과시키는것에 만족하지 않고 더 개선할 부분이 없는지 확인해보는 습관을 키워야 할 것 같습니다.

profile
늦게배운 코딩이 무섭다

0개의 댓글