[JS] 2021카카오 : 거리두기 확인하기 프로그래머스 LEVEL2

---

문제 링크

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

풀이 전략

대기실은 5개이며, 각 대기실은 5x5 크기입니다.
거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

P를 하나의 정점으로 생각하여 dfs또는 bfs로 탐색하면 될듯하였다. 공간이 5 * 5로 정해져있기 때문에 부담없이 떠올릴 수 있었다. 

코드 

function solution(places) {
    const answer_arr = [];

    for (const t_case of places) {
        const startXY = [];

        for (let i = 0; i < 5; i++) {
            for (let j = 0; j < 5; j++) {
                if (t_case[i][j] === "P") {
                    startXY.push([i, j]);
                }
            }
        }

        answer_arr.push(bfs(t_case, startXY));
    }

	return answer_arr;
}

function bfs(graph, startXY) {
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];

    for (const [fx, fy] of startXY) {
        const queue = [];
        const visited = Array.from({ length: 5 }, () =>
            Array.from({ length: 5 }, () => 0)
        );
        const dis_arr = Array.from({ length: 5 }, () =>
            Array.from({ length: 5 }, () => 0)
        );
        queue.push([fx, fy]);
        visited[fx][fy] = 1;

        while (queue.length) {
            const [x, y] = queue.shift();

            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (
                    0 <= nx &&
                    nx < 5 &&
                    0 <= ny &&
                    ny < 5 &&
                    !visited[nx][ny]
                ) {
                    if (graph[nx][ny] === "O") {
                        visited[nx][ny] = 1;
                        queue.push([nx, ny]);
                        dis_arr[nx][ny] = dis_arr[x][y] + 1;
                    } else if (graph[nx][ny] === "P" && dis_arr[x][y] <= 1) {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}

 

회고

도움받은 블로그

각 P의 경우의 수를 모두 고려하여 보아야하기 때문에 이점을 가장 유의해야한다. 
중요한 점은 본디나온 p의 위치에서 다른 P를 발견했을 때 각 정점간의 거리를 구하는 것이다. 이때, queue에 값을 하나더 추가해 주어도되고 5 * 5로 정해져있기 때문에 배열을 사용해도 된다. 

처음 문제를 만났을 땐 막막했는데, 어떤 문제유형인지 알고 접근하니 쉽게 풀렸다. 실전에서 이런생각을 해낼 수 있을진 모르겠지만.... 계속 풀어봐야겠다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)