[JavaScript] 거리두기 확인하기

level : 2

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

My Solution(1) - test case 1개 미통과

function IsRight(pos1,pos2){
    return Math.abs(pos1[0]-pos2[0])+Math.abs(pos1[1]-pos2[1]) > 2 ? true : false;
}
function IsPartition(pos1,pos2,arr){
    if(Math.abs(pos1[0]-pos2[0])+Math.abs(pos1[1]-pos2[1])===1)
        return false;
    if(pos1[0]===pos2[0]){
        const temp1 = pos1[1]>pos2[1] ? pos2[1]:pos1[1];
        const temp2 = pos1[1]>pos2[1] ? pos1[1]:pos2[1];
        for(let i = temp1+1; i <temp2; i++){
            if(arr[pos1[0]][i]==='X')
                return true;
        }
    }
    else if(pos1[1]===pos2[1]){
        const temp1 = pos1[0]>pos2[0] ? pos2[0]:pos1[0];
        const temp2 = pos1[0]>pos2[0] ? pos1[0]:pos2[0];
        for(let i = temp1+1; i < temp2; i++){
            if(arr[i][pos1[1]]==='X')
                return true;
        }
    }
    const temp1 = pos1[0]>pos2[0] ? pos2[0]:pos1[0];
    const temp2 = pos1[1]>pos2[1] ? pos2[1]:pos1[1];
    if(arr[temp1][temp1 === pos1[0] ? pos2[1] : pos1[1]]==='X'&&arr[temp2 === pos1[1] ? pos2[0] : pos1[0]][temp2]==='X')
        return true;
    
    return false;
    
}
function solution(places) {
    let answer = [];
    places.forEach((arr,index)=>{
        let queue = [];
        let IsOk = true;
        arr.forEach((str,i)=>{
            for(let j = 0; j < 5; j++)
                if(str[j]==='P')
                    queue.push([i,j]);
        })
        for(let i = 0; i < queue.length-1;i++){
            for(let j = i+1;j < queue.length;j++){
                if(!IsRight(queue[i],queue[j])){
                    if(!IsPartition(queue[i],queue[j],arr)){
                        IsOk = false;
                        break;
                    }
                }
            }
            if(!IsOk)
                break;
        }
        answer.push(IsOk?1:0);
    })
    return answer;
}

풀이방법(1)
IsRight이라는 function은 맨해튼 거리로 2초과인지 아닌지를 판별하는 function이다.

IsPartition이라는 function은 두 위치에 대하여 중간에 Partition으로 막혀 거리두기를 잘했는지 판별하는 function이다.

solution함수에서 고사장마다 아래와 같은 행위를 반복하였다.

1. queue는 빈 배열을 IsOk는 true를 넣는다. queue에는 'P'의 위치들을 넣을 것이고 IsOk는 거리두기를 잘 했는 지에 대한 여부를 판별하는 것이다.

2. queue이라는 배열에 'P'의 위치를 push하였다.

3. queue안에 있는 'P'의 위치들 중 2개를 차례대로 뽑아 IsRight으로 맨하튼 거리가 2이하인 두 개의 위치를 선정한다.

4. 선정된 두 위치를 IsPartition으로 거리두기를 잘 했는지 판별하고 true면 다른 위치를 선정한다. false면 IsOk라는 변수를 false로 바꾸고 반복문을 탈출한다.

5. IsOk가 false면 answer에 0을 true면 1을 push 한다.

중간 test case중 11번에 막혔다. 반례를 찾으려고 했지만 도저히 찾기가 힘들었다.

단 한 개의 test case에 걸렸지만 어디서 틀린지 몰라 다시 풀기로 했다.

 

My Solution(2)

function solution(places) {
    let answer = [];
    places.forEach((matrix,index)=>{
        let IsOk = true;
        matrix.forEach((str,i)=>{
            str.split('').forEach((val,j)=>{
                if(val==='P'){
                    let queue = [];
                    if(i>0){
                        if(matrix[i-1][j]==='O')
                            queue.push([i-1,j]);
                        else if(matrix[i-1][j]==='P')
                            IsOk = false;
                    }
                    if(i<4){
                        if(matrix[i+1][j]==='O')
                            queue.push([i+1,j]);
                        else if(matrix[i+1][j]==='P')
                            IsOk = false;
                    }
                    if(j>0){
                        if(matrix[i][j-1]==='O')
                            queue.push([i,j-1]);
                        else if(matrix[i][j-1]==='P')
                            IsOk = false;
                    }
                    if(j<4){
                        if(matrix[i][j+1]==='O')
                            queue.push([i,j+1]);
                        else if(matrix[i][j+1]==='P')
                            IsOk = false;
                    }
                    while(queue.length>0){
                        const [x,y] = queue.shift().map(Number);
                        if(x>0)
                            if(matrix[x-1][y]==='P'&&x-i!==1)
                                IsOk = false;
                        if(x<4)
                            if(matrix[x+1][y]==='P'&&i-x!==1)
                                IsOk = false;
                        if(y>0)
                            if(matrix[x][y-1]==='P'&&y-j!==1)
                                IsOk = false;
                        if(y<4)
                            if(matrix[x][y+1]==='P'&&j-y!==1)
                                IsOk = false;
                    }
                }
            })
        })
        answer.push(IsOk?1:0);
    })
    return answer;
}

풀이방법(2)

'P'의 위치에서 상하좌우에 값을 판별하고 'O'가 있으면 queue에 상하좌우의 좌표를 push하고 'P'가 있으면 IsOk라는 변수를 false로 바꾼다. queue에 있는 모든 좌표를 한번 더 상하좌우를 살펴 거기에 'P'가 있으면 IsOk를 false로 바꾼다. 이때, 이전에 갔던 경로는 확인하지 않는다.

IsOk가 true면 answer에 1을 false면 0을 push한다.

 

느낀점
두 번째 풀이로 통과를 하였지만 만약 맨하튼 거리가 3이상을 측정하는 문제가 나왔다면 코드가 매우 길어졌을 것이다.

다른 분들의 풀이를 보니 dfs와 bfs를 함수로 만들어서 사용하는 방법을 보고 익숙해 진다면 꼭 반복문이 아닌 비슷한 문제가 나오면 풀 수 있게 함수를 만들어야겠다고 생각을 했다.

또한 2번째 풀이에서 while문의 조건에 IsOk가 true인 경우도 추가하여 안 할 수 있는 경우는 반복문을 피해 메모리 사용을 줄일 수 있었을 거라는 생각이 들어 아쉬웠다.