ROW_SIZE = 5
COL_SIZE = 5
MIN_DIST = 2
DXY = [(0, -1), (0, 1), (-1, 0), (1, 0)]


def dfs(place, visited, x, y, dist):
    # 거리두기를 지킨 경우
    if (x, y) in visited \
            or x < 0 or x >= ROW_SIZE or y < 0 or y >= COL_SIZE \
            or dist > MIN_DIST \
            or place[y][x] == 'X':
        return 1

    # 거리두기를 지키지 않은 경우
    if dist > 0 and place[y][x] == 'P':
        return 0

    visited.add((x, y))

    for dx, dy in DXY:
        if dfs(place, visited, x + dx, y + dy, dist + 1) == 0:
            return 0

    return 1


def check_keeping_distance(place):
    ROW_SIZE = len(place[0])
    COL_SIZE = len(place)

    for i in range(ROW_SIZE):
        for j in range(COL_SIZE):
            if place[i][j] == 'P' and dfs(place, set(), j, i, 0) == 0:
                return 0

    return 1


def solution(places):
    answer = []

    for place in places:
        answer.append(check_keeping_distance(place))

    return answer


# 정확성  테스트
# 테스트 1 〉	통과 (0.12ms, 10.3MB)
# 테스트 2 〉	통과 (0.04ms, 10.4MB)
# 테스트 3 〉	통과 (0.07ms, 10.3MB)
# 테스트 4 〉	통과 (0.04ms, 10.3MB)
# 테스트 5 〉	통과 (0.04ms, 10.3MB)
# 테스트 6 〉	통과 (0.07ms, 10.3MB)
# 테스트 7 〉	통과 (0.05ms, 10.3MB)
# 테스트 8 〉	통과 (0.05ms, 10.3MB)
# 테스트 9 〉	통과 (0.06ms, 10.2MB)
# 테스트 10 〉	통과 (0.03ms, 10.3MB)
# 테스트 11 〉	통과 (0.04ms, 10.3MB)
# 테스트 12 〉	통과 (0.04ms, 10.3MB)
# 테스트 13 〉	통과 (0.05ms, 10.3MB)
# 테스트 14 〉	통과 (0.04ms, 10.3MB)
# 테스트 15 〉	통과 (0.03ms, 10.3MB)
# 테스트 16 〉	통과 (0.05ms, 10.3MB)
# 테스트 17 〉	통과 (0.05ms, 10.3MB)
# 테스트 18 〉	통과 (0.03ms, 10.4MB)
# 테스트 19 〉	통과 (0.13ms, 10.3MB)
# 테스트 20 〉	통과 (0.05ms, 10.2MB)
# 테스트 21 〉	통과 (0.03ms, 10.3MB)
# 테스트 22 〉	통과 (0.05ms, 10.3MB)
# 테스트 23 〉	통과 (0.02ms, 10.3MB)
# 테스트 24 〉	통과 (0.02ms, 10.3MB)
# 테스트 25 〉	통과 (0.02ms, 10.3MB)
# 테스트 26 〉	통과 (0.03ms, 10.3MB)
# 테스트 27 〉	통과 (0.04ms, 10.3MB)
# 테스트 28 〉	통과 (0.05ms, 10.2MB)
# 테스트 29 〉	통과 (0.05ms, 10.3MB)
# 테스트 30 〉	통과 (0.04ms, 10.3MB)
# 채점 결과
# 정확성: 100.0
# 합계: 100.0 / 100.0

assert (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"]]) == [1, 0, 1, 1, 1])
