programmers Level 2 거리두기 확인하기

문제

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

걸린 시간

-

풀이

JavaScript

function solution(places) {
    const answer = [];
    const dy = [1, -1, 0, 0];
    const dx = [0, 0, 1, -1];
    // n 차원 배열 생성 함수
    const n_array = (li, el) => {
        if(!li.length) return undefined;
        const func = (li, i, n, el) => {
            if(i === li.length-1){
                if(typeof el === 'object'){
                    const tmp = Array(li[i]);
                    for(let i = 0; i < li[i]; i++)
                        tmp[i] = JSON.parse(JSON.stringify(el))
                    return tmp;
                }
                else return Array(li[i]).fill(el);
            }
            else return Array.from(Array(li[i]), () => func(li, i+1, n, el))
        }
        return func(li, 0, li.length, el);
    }
    // dfs
    const dfs = (r, y, x, d, visited) => {
        // 응시자 확인
        let ret = 1;
        if(d && places[r][y][x] === 'P') ret = 0;
        // 재귀 호출
        if(d < 2){
            for(let i = 0; i < 4; i++){
                let ny = y+dy[i];
                let nx = x+dx[i];
                if(ny < 0 || ny >= 5 || nx < 0 || nx >= 5) continue;
                if(visited[ny][nx]) continue;
                if(places[r][ny][nx] !== 'X'){
                    visited[ny][nx] = true;
                    ret = Math.min(ret, dfs(r, ny, nx, d+1, visited));
                }
            }
        }
        return ret;
    }
    // 모든 대기실 조사
    for(let i = 0; i < 5; i++){
        let ans = 1;
        for(let y = 0; y < 5; y++){
            for(let x = 0; x < 5; x++){
                if(places[i][y][x] === 'P'){
                    const visited = n_array([5, 5], false);
                    visited[y][x] = true;
                    ans = Math.min(ans, dfs(i, y, x, 0, visited));
                }
            }
        }
        answer.push(ans);
    }
    return answer;
}

깊이가 2 인 dfs, bfs 탐색을 대기실의 모든 지원자 위치에서 한번씩 돌려주면 된다.