[Level2] 거리두기 확인하기

🛠 문제

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

👩🏻‍💻 해결 방법

bfs를 사용하여 풀 수 있는 문제다
bfs에서는 거리두기가 지켜지면 True, 지켜지지 않으면 False를 반환한다

소스 코드

from collections import deque

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

def bfs(place, i, j):
    q = deque()
    q.append((i, j, 0))
    
    visit = [[0] * 5 for _ in range(5)]
    visit[i][j] = 1
    
    while q:
        x, y, d = q.popleft()
        # 거리가 2이하에 응시자가 있을 경우
        if 0 < d < 3 and place[x][y] == 'P':
            return False
        # 거리가 2초과일 경우
        if d > 2:
            break
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            nd = d + 1
            
            if 0 <= nx < 5 and 0 <= ny < 5:
                # 파티션이 아니고 방문한 적 없을 경우
                if place[nx][ny] != 'X' and visit[nx][ny] == 0:
                    q.append((nx, ny, nd))
                    visit[nx][ny] = 1
    
    return True      

def solution(places):
    answer = []
    
    for place in places:
        chk = 0
        for i in range(len(place)):
            for j in range(len(place[0])):
                if place[i][j] == 'P':
                    if not bfs(place, i, j):
                        answer.append(0)
                        chk = 1
                        break
            if chk == 1:
                break
        else:
            answer.append(1)
            
    return answer