[javascript] 프로그래머스 - 거리두기 확인하기(2021 카카오 채용연계형 인턴십)

🤔문제 해결

• 한 방안의 모든 P에 대하여 차례로 주변을 탐색했다. 약간 BFS 느낌🤔
  • O를 만나면 계속탐색
  • P를 만나면 멈춘다. - 거리두기 지켜지지 않음
    • 탐색 중 P에 대하여 거리가 2가 되면 더 이상 그 지점에서는 탐색을 멈춘다.
    • 그러므로 탐색 중 다른 P를 만났다는 말은 거리가 2 이하이기 때문에 탈락
  • X는 무시

 

💨 파이썬으로 풀던 느낌으로 풀었다. break를 한번에 걸어주는 방법이 없나...

 

💻소스 코드

 function solution(places) {
    var answer = [];
    var length = places[0].length;
    var dx = [-1, 1, 0, 0]  // 상 하 좌 우
    var dy = [0, 0, -1, 1]

    for (var place of places) {
        var isRight = false;
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length; j++) {
                if (place[i][j] === 'P') {                  
                    // 크기가 같은 비어있는 2차원 배열
                    var placeDistance = Array.from(Array(length), () => new Array(length).fill(-1));
                    var stack = [[i, j]];
                    placeDistance[i][j] = 0;

                    while (stack.length > 0 && isRight === false) {
                        [cx, cy] = stack.pop();
                        if (placeDistance[cx][cy] == 2) continue; // 거리가 2만큼의 빈 공간이므로 체크할 필요 없음

                        for (let k = 0; k < dx.length; k++) {
                            var nx = cx + dx[k];
                            var ny = cy + dy[k];
                            if (nx >= 0 && nx < length && ny >= 0 && ny < length && placeDistance[nx][ny] == -1) {
                                if (place[nx][ny] === 'O') { // 빈 공간이면 거리 1 넣고
                                    placeDistance[nx][ny] = placeDistance[cx][cy] + 1;
                                    stack.push([nx, ny]);
                                } else if (place[nx][ny] === 'P') { // P를 만나면 거리 2 이내에 만났으므로 거리두기 지켜지지 않음
                                    stack = [];
                                    isRight = true;
                                    break
                                }

                            }
                        }
                    }
                    if(isRight) break;
                }
                if(isRight) break;
            }
        }
        if (isRight) {
            answer.push(0);
        } else {
            answer.push(1);
        }
    }
    return answer;
}
console.log(solution([["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]));

 

📕문제 확인

출처: 프로그래머스