programmers. 거리두기 확인하기

문제

링크

코딩테스트 연습 - 거리두기 확인하기

풀이

주어진 조건을 구현하는 문제

배열에서 사람이 앉아있는 자리 P를 찾은 후

문제에서 제시한 맨해튼 거리가 2이내에 다른 P가 없다면 거리두기를 한 것이고 P가 있다면 거리두기를 하지 않은 것이다

단, 거리 내에 P가 있다고 해도 그 사이에 X인 파티션으로 가로막혀있다면 거리두기를 한 것으로 친다

맨해튼 거리 2이내 좌표는 상하좌우, 대각선 그리고 현재 좌표에서 직선으로 2칸만큼 떨어진 곳들에 해당한다

현재 좌표가 0 (2,2)일 때 맨해튼 거리를 나타낸 그림

위 그림에서 회색과 노란색에서 P를 찾고 조건을 확인하면된다

나는 다음과 같이 구현했다

1. 2차 배열을 순회하며 P를 찾는다
2. 찾은 좌표에서 상,하,좌,우 를 탐색해서 P인지 확인한다 (이 경우 파티션 여부에 상관없이 거리두기를 하지 않은 것이므로 0을 리턴)
3. 2에서 P를 찾지 못했다면 좌상, 우상, 좌하, 우하를 탐색해서 P인지 확인한다 (이 때 P를 발견했다면 1에서 찾은 좌표와 P를 발견한 좌표 사이에 X가 있다면 거리두기를 한 것, 그렇지 않다면 0을 리턴)
4. 3에서도 조건을 만족했다면 직선 거리가 2인 좌표(대각선을 제외한 노란색 부분)을 탐색한다 (이 때 P를 발견했다면 그 사이에 X가 있는지 확인)

코드

    function solution(places) {
        var answer = [];

        places.forEach(v=>{
            const room = v.map(v=>v.split(''));

            answer.push(findP(room));
        });

        return answer;
    }


    function findP(arr){
        const N = 5;

        for(let i=0; i<N;i++){
            for(let j=0; j<N;j++){
                if(arr[i][j]==='P'){
                    if(!checkCrossSeats([i,j],arr)) return 0;
                    if(!checkDiagonalSeats([i,j],arr)) return 0;
                    if(!checkD2Seats([i,j],arr)) return 0;
                }
            }
        }
        return 1;
    }

    function checkCrossSeats([y,x], arr){
        const cross = [[-1,0], [0,1], [1,0], [-1,0]];

        for(let i=0; i<cross.length;i++) {
            const a = y + cross[i][0];
            const b = x + cross[i][1];

            if (a < 0 || b < 0 || a >= arr.length || b >= arr.length) continue;
            if (arr[a][b] === 'P') return false;

        }
        return true;
    }

    function checkDiagonalSeats([y,x],arr){
        const diagonal = [[-1,-1], [-1,1], [1,-1], [1,1]];

        for(let i=0; i<diagonal.length;i++) {
            const a = y + diagonal[i][0];
            const b = x + diagonal[i][1];

            if (a < 0 || b < 0 || a >= arr.length || b >= arr.length) continue;
            if (arr[a][b] === 'P' && i===0) {
                if(!(arr[a+1][b] === 'X' && arr[a][b+1] ==='X')) return false;
                continue;
            }
            if (arr[a][b] === 'P' && i===1) {
                if(!(arr[a+1][b] === 'X' && arr[a][b-1] ==='X')) return false;
                continue;
            }
            if (arr[a][b] === 'P' && i===2) {
                if(!(arr[a-1][b] === 'X' && arr[a][b+1] ==='X')) return false;
                continue;
            }
            if (arr[a][b] === 'P' && i===3) {
                if(!(arr[a-1][b] === 'X' && arr[a][b-1] ==='X')) return false;
            }
        }
        return true;
    }

    function checkD2Seats ([y,x],arr) {
        const d2 = [[2,0], [0,2], [-2,0], [0,-2]];

        for(let i=0; i<d2.length;i++) {
            const a = y + d2[i][0];
            const b = x + d2[i][1];

            if (a < 0 || b < 0 || a >= arr.length || b >= arr.length) continue;
            if (arr[a][b] === 'P' && i===0) {
                if(arr[a-1][b]!=='X') return false;
                continue;
            }
            if (arr[a][b] === 'P' && i===1) {
                if(arr[a][b-1]!=='X') return false;
                continue;
            }
            if (arr[a][b] === 'P' && i===2) {
                if(arr[a+1][b]!=='X') return false;
                continue;
            }
            if (arr[a][b] === 'P' && i===3) {
                if(arr[a][b+1]!=='X') return false;
            }
        }
        return true;
    }