[프로그래머스 - 2021 카카오 인턴] - 거리두기 확인하기

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

프로그래머스

 

문제 설명이 길어서 자세한 설명은 링크를 참고하자

5x5크기의 강의실들이 있고, 각 강의실에서 거리두기를 지키기 위해 응시자들 간의 맨해튼 거리가 2이하여야 한다.

 

 

문제 풀이 과정은

• 각 강의실 별로 거리두기 검사
  • 각 강의실의 응시자들의 위치를 시작점으로 BFS 호출
    • 거리 2까지만 검사해준다 (가장 중요!!!)
    • up, down, left, right별로 한칸씩 움직였을 때, 해당 위치에 응시자가 있다면 거리두기가 지켜지지 않음
    • X(파티션)이 있는 위치는 검사하지 않는다.
  • BFS 결과 거리두기가 지켜지지 않은 사람이 있으면 바로 리턴
  • 모든 응시자를 검사해도 이상 없으면 리턴
• 강의실 검사 결과를 answer에 저장해준다.

 

파이썬의 collections 패키지의 deque()를 사용해서 큐 자료구조를 사용했다.

큐에 탐색 노드를 집어넣을 땐 [ i위치, j위치, 출발지로부터거리 ]의 값을 넣어주었다.

 

import collections

def bfs(place,i,j):
    dq = collections.deque()
    visited = [[0 for j in range(5)] for i in range(5)]
    dq.append([i,j,0])
    visited[i][j] = 1
    while dq:
        i,j,dist = dq.popleft() # 좌표,거리
        up, down = i-1, i+1
        left, right = j-1, j+1
        if dist < 2:
            if i > 0 and visited[up][j]==0 and place[up][j]=="P":
                return 1
            elif i > 0 and visited[up][j]==0 and place[up][j]=="O":
                dq.append([up,j,dist+1])
            if i < 4 and visited[down][j]==0 and place[down][j]=="P":
                return 1
            elif i < 4 and visited[down][j]==0 and place[down][j]=="O":
                dq.append([down,j,dist+1])
            if j > 0 and visited[i][left]==0 and place[i][left]=="P":
                return 1
            elif j > 0 and visited[i][left]==0 and place[i][left]=="O":
                dq.append([i,left,dist+1])
            if j < 4 and visited[i][right]==0 and place[i][right]=="P":
                return 1
            elif j < 4 and visited[i][right]==0 and place[i][right]=="O":
                dq.append([i,right,dist+1])

# 강의실의 각 응시자를 시작점으로 BFS
def check(place):
    for i in range(5):
        for j in range(5):
            if place[i][j] == "P":
                if bfs(place,i,j) == 1: # 거리두기 지켜지지 않은 사람이 있으면
                    return 0
    return 1 # 다 살펴봐도 이상 없으면

def solution(places):
    answer = []
    for place in places:
        if check(place) == 1: # 거리두기 지켜지면
            answer.append(1)
        else: # 거리두기 지켜지지 않으면
            answer.append(0)
    return answer