[프로그래머스][bfs] 거리두기 확인하기

     

목차

 

 

문제

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

프로그래머스

 

 

문제 구현 방향

P인 경우를 모든 시작점으로 x이면 탐색을 멈추는 식으로 bfs를 구현하면 된다. 이때 다음을 주의해야 한다.

처음에 거리를 visit[i][j] = visit[i][j] +1 로 한뒤 거리가 2 이내면 탐색을 종료시켜 틀린 문제이다.

이렇게 하면 모든 경우를 다 탐색할 수 없으니 거리 배열을 따로 하고 P를 만났을 때 거리가 2이내면 0을 반환하는 식으로 풀어야 한다.

 

 

잘못된 풀이

let dir = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
];

function solution(places) {
    var answer = [];
   
    places.forEach((plc) => {
        let board = [];
        plc.forEach((item)=>board.push(item.split("")));
        let flag =1;
        for (let i = 0; i < board.length; i++) {
            if(!flag)break;
            for (let j = 0; j < board.length; j++) {
                if (board[i][j] === "P") flag = bfs(j, i, board);
            }
        }
        answer.push(flag);
    });

    return answer;
}

function bfs(startX, startY, board) {
    let queue = [];
    let visit = Array.from({ length: board.length }, () =>
        Array(board[0].length).fill(0)
    );
    queue.push([startX, startY]);
    visit[startY][startX] = 1;
    while (queue.length) {
        let [x, y] = queue.shift();
        if(visit[y][x] >= 3)continue;
        for (let dr of dir) {
            let nx = x + dr[0];
            let ny = y + dr[1];
            if (nx > board[0].length-1 || nx < 0 || ny > board.length-1 || ny < 0)
                continue;
            if (board[ny][nx] === "X" || visit[ny][nx]) continue;
            if (board[ny][nx] === 'P' && visit[y][x] + 1 <= 2) return 0;
            visit[ny][nx] = visit[y][x] + 1;
            queue.push([nx, ny]);
        }
    }
    return 1;
}

 

 

코드 구현

let dir = [
    [1, 0],
    [0, -1],
    [-1, 0],
    [0, 1],
];

function solution(places) {
    var answer = [];
    for (let place of places) {
        let cnt = 1;
        let board = [];
        place.forEach((item) => board.push(item.trim().split("")));
        for (let i = 0; i < 5; i++) {
            for (let j = 0; j < 5; j++) {
                if (board[i][j] === "P" && cnt) cnt = bfs(j, i, place);
            }
        }
        answer.push(cnt);
    }

    function bfs(startX, startY, board) {
        let queue = [];
        queue.push([startX, startY]);
        let visit = Array.from({ length: 5 }, () => Array(5).fill(0));
        let degree = Array.from({ length: 5 }, () => Array(5).fill(0));
        visit[startY][startX] = 1;

        while (queue.length) {
            let [x, y] = queue.shift();
            for (let dr of dir) {
                let nx = x + dr[0];
                let ny = y + dr[1];
                if (nx < 0 || nx > 4 || ny < 0 || ny > 4) continue;
                if (board[ny][nx] === "X" || visit[ny][nx]) continue;
                if (board[ny][nx] === "P" && degree[y][x] + 1 <= 2) {
                    console.log(board, visit, degree);
                    return 0;
                }
                visit[ny][nx] = 1;
                queue.push([nx, ny]);
                degree[ny][nx] = degree[y][x] + 1;
            }
        }

        return 1;
    }

    return answer;
}