[Programmers] 거리두기 확인하기 (파이썬, Python)

https://pixabay.com/ko/photos/꽃-식물-선셋-노란-꽃-6339436/

 

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

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

해당 문제는 Programmers의 2021 카카오 채용연계형 인턴십 문제집에 속해 있는 문제입니다.

 

문제에서 주어지는 각 면접 대기실이 거리두기 규칙을 지키고 있는지 판단하는 것이 문제의 목표입니다.

 

면접 대기자는 서로 맨해튼 거리가 2 이하가 되는 자리에 앉으면 안 됩니다.

여기서 '맨해튼 거리가 2 이하'인 조건은 '너비 우선 탐색의 depth가 2 이하'인 조건과 같습니다.

 

따라서 각 면접 대기자마다 자리를 기준으로 depth가 2 이하인 곳에 다른 면접 대기자가 있는지 확인하면 거리두기 준수 여부를 판단할 수 있습니다.

 

탐색을 진행할 때, 면접 대기자 사이에 파티션이 있는 경우도 고려하여 거리두기 준수 여부를 판단해야 합니다.

해당 조건은 파티션 주변을 더 이상 탐색하지 않으면 됩니다.

즉, 파티션이 있는 자리를 queue에 넣지 않으면 구현이 됩니다.

 

전체 코드

from collections import deque

def check(place, sr, sc):
    res = 1
    
    dy, dx = (-1, 0, 1, 0), (0, 1, 0, -1)
    visited = [ [ False ] * 5 for _ in range(5) ]
    visited[sr][sc] = True
    
    que = deque([(sr, sc, 0)])
    
    while que:
        cr, cc, cd = que.popleft()
        
        for i in range(4):
            nr, nc = cr + dy[i], cc + dx[i]
            
            if 0 <= nr < 5 and 0 <= nc < 5 and not visited[nr][nc]:
                if place[nr][nc] == "O" and cd < 1:
                    visited[nr][nc] = True
                    que.append((nr, nc, cd+1))
                    
                else:
                    if place[nr][nc] == "P":
                        res = 0
                        break
            
            if res == 0:
                break

    return res

def solution(places):
    answer = []
    
    for place in places:
        is_safe = 1
        
        for i in range(5):
            for j in range(5):
                if place[i][j] == "P":
                    is_safe = check(place, i, j)
                    
                    if is_safe == 0:
                        break
                        
            if is_safe == 0:
                break
                
        answer.append(is_safe)
                
    return answer

---

읽어 주셔서 감사합니다 :)

잘못된 부분이 있다면 댓글로 편히 알려주세요😊