[파이썬] 카카오 2021 거리두기 확인하기

https://school.programmers.co.kr/learn/courses/30/lessons/81302

일반적인 BFS에서 한 가지 아이디어가 필요했다.
먼저 사람이 앉아있는 위치를 찾고 visited 배열을 선언한 후에 BFS를 출발한다.
BFS를 수행하기 위해 q가 필요하다.

                if p[i][j] == "P":
                    q.append((i, j))
                    v = [[0] * 5 for _ in range(5)]
                    v[i][j] = 1

만약 거리가 2 이하인 경우 경로상에 X가 없는 경우이면 실패한 경우로 본다.
elif p[y][x] !='X' and p[ny][nx] == "P":
한번이라도 실패하면 더 진행할 필요가 없므로 break 로 종료한다. while문도 함께 중료시키기 위해서 index를 while문 조건에 추가해주었다.
그게 아닌 경우 q에 다음 행선지를 추가하는데, 거리가 2가 넘지 않으면서 O 인 경우만 추가하하면 된다. (X인 경우는 더 이상 진행하지 않는다)

from collections import deque

def solution(places):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    answer = [True] * 5
    for ind, p in enumerate(places):
        p = [*map(list, p)]
        for i in range(5):
            for j in range(5):
                q = deque()
                if p[i][j] == "P":
                    q.append((i, j))
                    v = [[0] * 5 for _ in range(5)]
                    v[i][j] = 1
                    d = 0
                    while q and answer[ind]:
                        y, x = q.popleft()
                        for t in range(4):
                            ny = y + dy[t]
                            nx = x + dx[t]
                            if (
                                ny >= 5
                                or nx >= 5
                                or ny < 0
                                or nx < 0
                                or v[ny][nx]
                            ):
                                continue
                            elif p[y][x] !='X' and p[ny][nx] == "P":
                                print(f"{(ny,nx)} is too close to {(i,j)} at place {ind}")
                                answer[ind] = False
                                break
                            else:
                                v[ny][nx] == 1
                                if p[ny][nx] == 'O' and abs(ny-i)+abs(nx-j)<2:
                                    q.append((ny, nx))
    return list(map(int,answer))