[알고리즘/프로그래머스] - 거리두기 확인하기(python)

문제

bfs를 이용하여 문제를 풀었다.

만약 아무도 앉지 않은 자리이면 q에 추가했다.
cnt를 두어 거리를 계산했고, 2를 넘어가면 bfs를 끝냈다.

from collections import deque


dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(a):
    start = []

    for i in range(5):
        for j in range(5):
            if a[i][j] == 'P':
                start.append((i, j))

    for s in start:
        q = deque()
        q.append((s[0], s[1], 0))
        visited = [[0] * 5 for _ in range(5)]
        visited[s[0]][s[1]] = 1

        while q:
            x, y, cnt = q.popleft()
            if cnt > 2:
                break
            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y

                if 0 <= nx < 5 and 0 <= ny < 5:
                    if not visited[nx][ny]:
                        if a[nx][ny] == 'O':
                            q.append((nx, ny, cnt + 1))
                            visited[nx][ny] = 1
                        if a[nx][ny] == 'P':
                            if cnt < 2:
                                return 0
    return 1


def solution(places):
    answer = []
    for i in places:
        answer.append(bfs(i))
    return answer