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

from collections import deque

def solution(places):
    dirs = [(0,1), (0,-1), (1,0), (-1,0)]
    
    # 맨해튼 거리 체크 메소드
    def get_distance(p1, p2):
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    
    def check(p1):
        y, x = p1[0], p1[1]
        # 해당 place 변수 호출을 위해 nonlocal 선언
        nonlocal place
        
        # 확인할 좌석을 queue / 이미 확인한 좌석을 visited에 저장.
        queue, visited = deque(), set()
        queue.append((y, x))
        while queue:
            # 확인할 좌석 선택
            ty, tx = queue.popleft()
            visited.add((ty, tx))
            
            for dy, dx in dirs:
                ny, nx = ty + dy, tx + dx
                # 현재 위치에서 거리가 2 이하이고, 아직 확인하지 않은 좌석일 경우
                if 0 <= ny < len(place) and 0 <= nx < len(place[0]) \
                        and get_distance((y, x), (ny, nx)) <= 2 and (ny, nx) not in visited:
                    # 해당 좌석 확인했음을 체크
                    visited.add((ny, nx))
                    
                    # 비어 있을 경우, 확인할 좌석 queue에 저장.
                    if place[ny][nx] == "O":
                        queue.append((ny, nx))
                    
                    # 사람이 있는 경우 == 거리두기 위배. False 반환
                    elif place[ny][nx] == "P":
                        return False
        
        return True
                    
    answer = []
    
    for place in places:
        
        # 사람들의 현재 위치 기록.
        position = set()
        for y in range(len(place)):
            for x in range(len(place[0])):
                if place[y][x] == "P":
                    position.add((y, x))
                    
        # 사람들의 거리두기 여부 체크
        for p in position:
            if check(p) is False:
                answer.append(0)
                break
        else:
            answer.append(1)
    
    return answer