[2021 카카오 채용 연계형 인턴십] 거리두기 확인하기

주요 조건들을 체크하자.

- 맨해튼 거리가 2이하이면 탈락

- 테이블도 이동에 포함

- 파티션은 이동에 포함하지 않음

 

bfs로 접근.

from collections import deque

def bfs(place):
    start = []
    d = (1,0),(-1,0),(0,1),(0,-1)

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

    q = deque()          
    visited = [[False] * 5 for _ in range(5)]

    for s in start:
        q.append((s[0], s[1], 0))
        visited[s[0]][s[1]] = True
        while q: 
            x, y, dist = q.popleft()
            for dx, dy in d:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny]:
                    if place[nx][ny] == 'O':
                        visited[nx][ny] = 1
                        q.append((nx, ny, dist + 1))
                    if place[nx][ny] == 'P' and dist <= 1:
                        return 0             
    return 1

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