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

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

from collections import deque

def bfs(x,y,graph):
    visited = [[ 0 for _ in range(5)] for _ in range(5)]
    visited[x][y] = 1
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    q = deque([(x,y)])

    while q:

        now_x,now_y = q.popleft()

        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]

            if 0<=nx<5 and 0<=ny<5 and graph[nx][ny] == 'O':
                if not visited[nx][ny]:
                    visited[nx][ny] = visited[now_x][now_y] + 1
                    q.append((nx,ny))

            elif 0<=nx<5 and 0<=ny<5 and graph[nx][ny] == 'P':
                if not visited[nx][ny]:
                    visited[nx][ny] = visited[now_x][now_y] + 1
                    return visited[nx][ny]-1

    return 3


def solution(places):
    answer = []


    for pac in places:
        graph = []
        check = True
        for i in range(5):
            graph.append(list(pac[i]))
        for i in range(5):
            for j in range(5):
                if graph[i][j] == 'P':
                    if bfs(i,j,graph)<=2:
                        check = False


        if check:
            answer.append(1)
        else:
            answer.append(0)

    return answer


print(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"]]))

BFS를 활용하는 문제인 것 같다.

BFS 함수에서 P를 만나면 return 시작점과의 맨허튼 거리를 반환하고, 만약 while 반복문을 자연적으로 탈출했다면 3을 반환한다.

while문을 자연적으로 탈출했다는 의미는 P를 만나지 않았다는 뜻이므로 임의의 숫자인 3을 반환시켰다. (거리=2 라는 조건보다 1 큰 숫자)

그러고나서는 P점에서 bfs를 돌려서 하나라도 2 이하의 값이 나오면 check 항목을 False로 바꾸고 check 값에 따라 answer에 1이나 0을 추가했다.