[파이썬] 거리두기 확인하기 - 2021 카카오 채용연계형 인턴십 [CODING TEST #20]

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

 

 

 

모든 'P'점에 대해 탐색을 수행해야 하므로 BFS를 사용했다. 

사람의 위치를 person 리스트에 담고, queue = deque([start])를 만들어서 거리두기에 걸리는 케이스를 모두 찾는다.

distance는 실시간으로 start로부터의 거리를 저장하는 리스트이고,

visited는 방문 여부를 저장하는 리스트이다. 한 번 방문한 위치는 다시 가지 않는다.

그래서 테이블 'O'이면 visited를 1로 만들고 distance를 1 증가시키고, deque에 그 점을 push한다.

만일 사람 'P'를 만났는데 거리 제한에 걸렸다면 거리두기를 지키지 않은 것. 0을 반환한다.

queue를 모두 돌고 비었다면 거리 두기에 문제가 없었다는 뜻이다. 1을 반환한다.

 

from collections import deque
def bfs(place):
    person = []
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                person.append((i,j))
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for start in person:
        queue = deque([start])
        visited = [[0 for _ in range(5)] for _ in range(5)] # 방문 여부 CHECK
        distance = [[0 for _ in range(5)] for _ in range(5)] # 실시간 거리를 담는 LIST
        visited[start[0]][start[1]] = 1
        while queue:
            x,y = queue.popleft()
            for z in range(4): # 상,하,좌,우 CHECK
                nx = x + dx[z]
                ny = y + dy[z]
                # 배열 내 만족 + 방문 아직 안 한 곳 
                if nx >= 0 and ny >= 0 and nx < 5 and ny < 5 and visited[nx][ny] == 0: 
                    # Table 'O' : 빈 공간이므로 계속 진행.
                    if place[nx][ny] == 'O':
                        queue.append((nx,ny))
                        visited[nx][ny] = 1
                        distance[nx][ny] = distance[x][y] + 1
                    # Person 'P' : 거리가 2 이하면 거리두기 걸린 것. return 0
                    elif place[nx][ny] == 'P' and distance[x][y] < 2:
                        return 0
                    # Partition 'X' : 아예 가지도 못하므로 알아서 처리됨.
    # 모든 start에 대해 문제 없으면 거리두기 잘 된것. return 1
    return 1              

def solution(places):
    answer = []
    for place in places:
        answer.append(bfs(place))
    return answer