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

from collections import deque

direction = [[1,0], [-1,0], [0,1], [0,-1]]
def solution(places):
    def bfs(r, c, visited):
        q = deque([[r,c,0]])
        while q:
            x, y, deph = q.popleft()
            
            for d in direction:
                n_x, n_y = x+d[0], y+d[1]
                if 0 <= n_x < 5 and 0 <= n_y < 5:
                    if visited[n_x][n_y]:
                        continue
                    if place[n_x][n_y] == 'P':
                        if deph < 2:
                            return True
                    if place[n_x][n_y] == 'O':
                        visited[n_x][n_y] = True
                        q.append([n_x, n_y, deph+1])
        return False
        
    answer = []
    
    for place in places:
        
        flag = False
        for i in range(len(place)):
            visited = [[False] * 5 for _ in range(5)]
            for j in range(len(place[0])):
                if(place[i][j] == 'P') and not visited[i][j]:
                    visited[i][j] = True
                    if bfs(i,j, visited):
                        flag = True
                        break
            if flag:
                answer.append(0)
                break
                
        else:
            answer.append(1)
        
    return answer

주어진 배열의 행, 열의 크기가 5이므로 완전탐색으로 풀이
완전탐색은 bfs로 수행 -> P에서 bfs를 진행하는데 P를 만날때 진행 깊이가 2 이하이면 거리두기가 되지 않은 상태이므로 answer에 0을 저장한다.