Python - [프로그래머스]81302-거리두기 확인하기

출처

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

문제

자세한 설명은 문제 참조

거리두기 규칙이 주어지고, 현재 대기실의 상황이 주어진다. 한 대기실에 참가자들이 잘 앉아있는지, 위반한 사람이 있는지를 판단하는 문제이다.

접근 방법

규칙을 보면, 상 하 좌 우 네방면에서 붙어있으면 안되고, 한 파티션으로 막혀 있지 않으면 대각선, 두칸 옆도 허용하지 않는다. |x1 - x2| + |y1 - y2| < 3을 만족해야 한다. 맵에 직접 그려보면 알기 쉽겠지만, 우리가 평소 BFS에서 특히 그래프에서 많이 사용하는 dx, dy를 중첩하여 두번 활용하면 되는 문제이다.

다시 말해, 상 하 좌 우 한방면으로 가서 그 장소에서 다시 원위치를 제외하고 상하 좌우중 3방면을 탐색하면 대각선과 2칸 옆자리를 모두 다시 탐색할 수 있게 된다.

풀이

대기실 별로 큰 for문을 구성해준다.
그 뒤 대기실 별로 현재 사람이 있는 위치를 queue에 넣어주고, BFS로직을 사용하여 탐색을 진행한다.
nx, ny위치로 이동 후 검사 -> 한번 더 nnx, nny (원래 x, y는 제외하도록 함) 이동 후 검사

하나라도 규칙이 위반된 경우를 발견한다면 find 변수를 0으로 바꾸고 break문을 통해 탈출하도록 구성하였다.

코드

from collections import deque
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
def is_range(x, y):
    return 0 <= x < 5 and 0 <= y < 5

def solution(places):
    answer = []
    sol =[]
    for room in places:
        queue = deque()
        for i in range(5):
            for j in range(5):
                if room[i][j] == 'P':
                    queue.append((i,j))
        find = 1
        while queue and find == 1:
            x, y = queue.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if is_range(nx, ny) and room[nx][ny] != 'X':
                    if room[nx][ny] == 'P': #바로 옆에 앉은 경우
                        find = 0
                        break
                    for j in range(4): ## 대각선, 두칸 옆 검사
                        nnx,nny = nx + dx[j], ny + dy[j]
                        if is_range(nnx, nny) and not (x == nnx and y == nny):
                            if room[nnx][nny] == 'P':
                                sol.append((nx, ny))
                                find = 0
                                break
                if find == 0:
                    break
        answer.append(find)
        queue.clear()
                    
                        
                
    return answer