프로그래머스 거리두기 확인하기 python, java

모든 사람에 대해 BFS를 돌리되, 거리가 2까지만 확인했다.
그이상은 사람이 있던 없던 상관 없으므로 무시해도 된다.

📜 문제 바로 가기 : 거리두기 확인하기

제출코드

파이썬

from collections import deque

def solution(places):
    def check(k):
        room = places[k]
        for i in range(5):
            for j in range(5):
                if room[i][j] == "P" and BFS(k, i, j) == False:
                    return 0
        return 1
    
    def BFS(k, i, j):
        room = places[k]
        visited = [[False] * 5 for _ in range(5)]
        que = deque([(i, j, 0)])
        visited[i][j] = True
        while que:
            i, j, d = que.popleft()
            if d >= 2:
                return True
            
            for di, dj in delta:
                ni, nj = i+di, j+dj
                if isRange(ni, nj) and visited[ni][nj] == False and room[ni][nj] != "X":
                    if room[ni][nj] == "P":
                        return False
                    que.append((ni, nj, d+1))
                    visited[ni][nj] == True
    
    def isRange(i, j):
        if 0 <= i < 5 and 0 <= j < 5:
            return True
        return False
            
    delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    answer = []    
    for k in range(len(places)):
        answer.append(check(k))
    
    return answer

자바

import java.util.ArrayDeque;

class Solution {
    static String[][] places;
    static int[][] delta = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};

    public int[] solution(String[][] pla) {
        places = pla;

        int[] answer = new int[5];
        for (int i=0; i < 5; i++) {
            answer[i] = check(i);
        }
        return answer;
    }
    
    public int check(int k) {
        String[] room = places[k];
        for (int i=0; i<5; i++) {
            for (int j=0; j<5; j++) {
                if ((room[i].charAt(j) == 'P') && (BFS(k, i, j) == false)) {
                    return 0;
                }
            }
        }
        return 1;

    }
    
    public boolean BFS(int k, int si, int sj) {
        String[] room = places[k];
        int[][] visited = new int[5][5];
        ArrayDeque<Node> que = new ArrayDeque();
        que.add(new Node(si, sj, 0));
        visited[si][sj] = 1;
        
        while (que.isEmpty() == false) {
            Node node = que.pollFirst();
            if (node.d >= 2) {
                return true;
            }
            
            for (int i = 0; i < 4; i++) {
                int di = delta[i][0] + node.i;
                int dj = delta[i][1] + node.j;
                if (isRange(di, dj) && visited[di][dj] == 0 && room[di].charAt(dj) != 'X') {
                    if (room[di].charAt(dj) == 'P') {
                        return false;
                    }
                    visited[di][dj] = 1;
                    que.add(new Node(di, dj, node.d+1));
                }
                
            }
            
        }
        return true;

    }
    
    public boolean isRange(int i, int j) {
        if (0 <= i && i < 5 && 0 <= j && j < 5) {
            return true;
        }
        return false;
    }
}

class Node {
    int i;
    int j;
    int d;
    
    public Node(int i, int j, int d) {
        this.i = i;
        this.j = j;
        this.d = d;
    }
}

---

접근방법

파티션으로 분리 되어 있다면 거리가 2이하여도 거리두기라고 봐도 된다고 하였는데 굳이 어렵게 예외등을 처리할 필요는 없었다. 단순히 미로찾기 문제처럼 파티션으로 벽으로 생각해준다면 벽을 돌아갈 경우 무조건 거리가 2가 넘는다.

따라서 파티션을 벽으로 생각하고 BFS를 돌리다가 거리가 2 이하인데 사람을 만나는 경우를 고려해주면 되겠다.