거리두기 확인하기

2021 카카오 채용연계형 인턴십

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

소요 시간 : 1시간 10분

실행 결과 : 실패

---

응시자끼리 멘해튼 거리가 2이하로 앉지 않아야한다. 단, 예외조건이 있다. 예외조건은 문제에 명시되어있다.

응시자가 앉아있는 자리라면 해당 자리에서 4방향 탐색을 진행한다. 방향 탐색 중, 다음 방향에 "X"가 되어있다면 즉, 파티션이 있다면 해당 방향으로는 더 탐색하지 않아도 된다. 하지만 "P"가 있다면 멘해튼 거리가 1이므로 규칙을 지키지 않은 경우가 된다. 만약 "O"가 있다면 응시자들끼리 파티션으로 막혀있지 않아 멘해튼 거리가 2가 될 수 있기 때문에 한번 더 4방향탐색을 진행해야한다.

 

해당 설계를 dfs재귀함수로 구현하려고 했는데 계속해서 올바르지 않은 결과가 나왔다.

로직은 맞는 거 같은데... 문제 원인을 찾지 못했다.

 

구현

방향탐색을 최대 두번만 진행하면 되기 때문에 반복문으로 구현할 수 있다.

function solution(places) {
    let ret = [];
    for(const place of places){
        let correct = 1;
        for(let i = 0; i<5; i++){
            for(let j = 0; j<5; j++){
                if(place[i][j] === "P"){
                    if(!solve(place, i, j)){
                        correct = 0;
                        break;
                    }
                }
            }
            if(!correct) break;
        }
        ret.push(correct);
    }
    return ret;
}

function solve(map, y, x){
    const dy = [-1, 0, 1, 0];
    const dx = [0, 1, 0, -1];
    for(let i = 0; i<4; i++){
        const ny = y + dy[i];
        const nx = x + dx[i];
        if(ny<0||ny>=5||nx<0||nx>=5) continue;
        if(map[ny][nx] === 'P') return false;
        if(map[ny][nx] === 'O'){
            for(let i = 0; i<4; i++){
                const ny2 = ny + dy[i];
                const nx2 = nx + dx[i];
                if(ny2<0||ny2>=5||nx2<0||nx2>=5||ny2 === y && nx2 === x) continue;
                if(map[ny2][nx2] === 'P') return false; 
            }
        } 
    }
    return true;
}