[프로그래머스 | Lv2] 거리두기 확인하기 (Python) - 2021 카카오 채용연계형 인턴십

 

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

프로그래머스

 

대기실은 5개이고, 5*5 크기로 고정된 사이즈로 주어졌기 때문에 구현이 까다롭지 않은 문제였다.

응시자들끼리는 맨해튼 거리가 2 이하로 앉지 말아야 하는데, 그 사이에 파티션이 존재하는 경우 앉을 수 있다.

입력된 배열을 대기실 별로 나누어 bfs를 수행했다.

 

먼저 P인 곳의 좌표를 모두 큐에 넣는다.

큐에서 하나씩 빼서 상하좌우를 돌면서

P인 곳이 존재하면 0을 리턴하고, (자리 사이가 맨해튼 거리1인 경우)

O인 곳이 존재하면 다시 상하좌우를 탐색하여 P인 곳이 두 곳 이상이면 0을 리턴하도록 했다.

(자리 사이가 맨해튼 거리2이고 사이에 빈 테이블이 있는 경우)

위의 어떠한 조건문에도 걸리지 않았다면 거리두기에 성공한 것이기 때문에 최종적으로 1을 리턴한다.

 

# 프로그래머스 81302: 거리두기 확인하기 (2021 카카오 채용연계형 인턴십)

from collections import deque

def bfs(place):
    queue = deque()
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P': # 좌표 'P'인 곳 모두 큐에 삽입
                queue.append([i, j])
    
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while queue:
        x, y = queue.pop()
        for i in range(4): # 상하좌우 탐색
            dx = x + move[i][0]
            dy = y + move[i][1]
            if 0 <= dx < 5 and 0 <= dy < 5:
                if place[dx][dy] == 'P': # 좌표가 'P'인 곳이 존재하면 거리두기 실패
                    return 0
                if place[dx][dy] == 'O': # 좌표가 'O'인 곳이 존재하면 상하좌우 한번 더 탐색
                    cnt = 0
                    for j in range(4):
                        mx = dx + move[j][0]
                        my = dy + move[j][1]
                        if 0 <= mx < 5 and 0 <= my < 5:
                            if place[mx][my] == 'P': # 좌표가 'P'인 곳의 개수 카운팅
                                cnt += 1
                        if cnt >= 2: # 좌표가 'P'인 곳이 두 곳 이상이면 거리두기 실패
                            return 0
    
    return 1
     
def solution(places):
    answer = []
    for place in places:
        answer.append(bfs(place))
    
    return answer