[Programmers] 거리두기 확인하기 문제 - (javascript)

문제 이름 :  거리두기 확인하기

---

 

<<< 문제 내용 >>>

---

 

function dfs(y, x, array){
    const dy = [-1,1,0,0];
    const dx = [0,0,-1,1];
    
    let queue = [];
    let visited = Array.from(Array(5), () => new Array(5).fill(0));
    let tempqueue = [[y, x]];
    let cnt = 0;
    
    while(cnt<2){
        queue = [...tempqueue];
        tempqueue = [];
        cnt+=1;
        
        while(queue.length>0){
            let [y, x] = queue.shift();
            
            visited[y][x] = 1;

            for(let i=0; i<4; i++){
                let ay = y+dy[i];
                let ax = x+dx[i];
                
                if(ay<0 || ay>=5 || ax<0 || ax>=5) continue;
                
                if(visited[ay][ax] === 0 && array[ay][ax] === 'O'){
                    tempqueue.push([ay, ax]);
                }

                if(visited[ay][ax] === 0 && array[ay][ax] === 'P'){
                    console.log(`ay = ${ay}, ax = ${ax}, cnt = ${cnt}`);
                    return false;
                }
            }
        }
    }
    
    return true;
}

function trueOrFalse(arr, answer){
    for(let i=0; i<5; i++){
        for(let j=0; j<5; j++){
            if(arr[i][j] === 'P'){
                if(dfs(i, j, arr) === false) return false;
            }
        }
    }
    
    return true;
}

function solution(places) {
    let answer = [];
    
    
    
    for(let i of places){
        let temp = [];
        
        for(let j of i){
            temp.push(j.split(''));
        }
    }
    
    for(let arr of places){
        trueOrFalse(arr,answer) ? answer.push(1) : answer.push(0);
    }
    
    return answer;
}

* trueOrFalse 는 places의 각 배열마다 얘가 거리두기가 된건지 안된건지 판단 후 알려주는 용도이고, dfs는 거리가 2이하일때 P를 만나는지를 체크해줍니다.

 

다른 사람들의 풀이 방식으로는 거리가 2이하인게 고정이 되어있다보니, dfs가 아닌 그냥 가로세로는 2칸, 대각선은 1칸씩 고려하여 찾는 방식으로 푼 것 같았습니다.

 

저는 이 방법이 떠오르지않아 dfs로 풀었고, 거리 2이하를 염두에 두려다보니 큐에 넣고 바로바로 처리하는 것이 아닌 턴제게임처럼 한 턴에 내가 갈수있는 위치를 다 저장하고, cnt를 올린 후 다음 위치를 이동하게끔 하면서 처리했습니다.

 

while문이 2번이지만 실제로 cnt가 3이상은 올라가지 않으니 작동횟수는 최대 2번입니다. 다만 깊은복사를 이용해 배열을 두개나 이용하였기 때문에 리소스가 조금 낭비되긴 하는 것 같습니다.

 

 

 

도움이 되셨다면 공감 부탁드립니다.