거리두기 확인하기

문제 파악

주어진 5x5배열에서 사람들이 앉아 있는 좌석 배치가 주어졌을 때, 거리두기가 잘 이루어졌는지 확인하는 문제이다. 각 좌석은 “P” 빈 공간은 “O”, 파티션은 “X” 이다. 각 “P” 의 거리가 맨하탄 거리 2 이상 이여야하고, 맨하탄 거리2 이내이더라도 파티션이 있다면 거리두기를 지킨것으로 간주한다.

접근 방법

BFS로 탐색(거리가 2이상이면 탐색 종료)

1. 각 좌석 배치에 대해 탐색을 시작한다.
2. “P”를 만나면 해당 위치를 기준으로 BFS를 수행하여 맨하탄 거리가 2이하인 사람이 인접해있는지 확인한다.

코드 구현

from collections import deque

def solution(places):
    answer = []
    
    
    def in_range(x, y):
        return 0 <= x < 5 and 0 <= y < 5
        
    
    def bfs(x, y, board):
        q = deque()
        visited = [[False] * 5 for _ in range(5)]
        
        q.append((x, y, 0))
        
        delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        
        # BFS 수행
        while q:
            cur_x, cur_y, cur_d = q.popleft()
            visited[cur_x][cur_y] = True
            # 맨허튼 거리 이상이면 BFS 중단
            if cur_d >= 2:
                continue 
            for dx, dy in delta:
                next_x, next_y = cur_x + dx, cur_y + dy
                if in_range(next_x, next_y) and not visited[next_x][next_y] and board[next_x][next_y] != "X":
                    if board[next_x][next_y] == "P":
                        return False
                    else:
                        board[next_x][next_y] = cur_d + 1
                        q.append((next_x, next_y, cur_d + 1))
                        visited[next_x][next_y] = True
        return True
        
        
    def check_social_distance(board):
        for i in range(5):
            for j in range(5):
                # 현재 앉은 사람의 위치를 큐에 추가
                if board[i][j] == "P":
                    if not bfs(i, j, board):
                        return False
        return True
    
    
    for place in places:
        board = []
        for row in place:
            board.append(list(row))
        if check_social_distance(board):
            answer.append(1)
        else:
            answer.append(0)
                        
    
    return answer