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

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def find(place):
    p = []
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                p.append((i, j))
    for i in range(len(p)):
        u, v = p[i]
        check = [[-1] * 5 for _ in range(5)]
        q = deque()
        q.append((u, v))
        check[u][v] = 0
        while q:
            x, y = q.popleft()
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                if 0 <= nx < 5 and 0 <= ny < 5:
                    if check[nx][ny] == -1 and place[nx][ny] != 'X':
                        q.append((nx, ny))
                        check[nx][ny] = check[x][y] + 1
        for j in range(i+1, len(p)):
            if check[p[j][0]][p[j][1]] != -1 and check[p[j][0]][p[j][1]] <= 2:
                return 0
    return 1

def solution(places):
    answer = []
    for place in places:
        answer.append(find(place))
    return answer