[PG/Python] 거리두기 확인하기

📌 문제

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

코딩테스트 연습 - 거리두기 확인하기

 

📌 문제 접근 방법

1. 각 대기실마다 함수를 사용하여 거리두기가 잘 되어있는 지 확인한 후, 0 또는 1을 answer에 append 했다.
2. 함수가 실행되면 우선 대기실 내의 사람의 위치를 people에 저장한다.
3. people을 하나씩 꺼내어 bfs를 통해 2 이내에 사람이 있는 지 확인한다. 만약 사람이 있다면 바로 False를 리턴한다.
4. people을 모두 확인했을 때 거리두기가 잘되어있다면 True를 리턴한다.

 

📌 코드

from collections import deque

def solution(places):
    def is_right(place):
        people = []
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    people.append((i, j))
        
        dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        for person in people:
            first_x, first_y = person[0], person[1]
            
            queue = deque()
            queue.append((first_x, first_y, 0))
            
            visited = [[0 for _ in range(5)] for _ in range(5)]
            visited[first_x][first_y] = 1
            
            while queue:
                x, y, dist = queue.popleft()

                if dist >= 2:
                    continue

                for dx, dy in dxy:
                    nx, ny = x+dx, y+dy

                    if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny]:
                        visited[nx][ny] = 1
                        
                        if place[nx][ny] == 'O':
                            queue.append((nx, ny, abs(first_x-nx)+abs(first_y-ny)))
                        elif place[nx][ny] == 'P':
                            return False
        
        return True
        
    answer = []
    for place in places:
        if is_right(place):
            answer.append(1)
        else:
            answer.append(0)
            
    return answer