[프로그래머스] 거리두기 확인하기 (level2, python)

 

 

🤔 풀이 코드

 

from collections import deque

def bfs(start, place):
    queue = deque()
    queue.append([start[0], start[1], 0])
    visited = [[False for _ in range(5)] for _ in range(5)]
    visited[start[0]][start[1]] = True
    
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    candidate = []
    
    while queue:
        a, b, dist = queue.popleft()
        
        for i in range(4):
            nx = dx[i] + a
            ny = dy[i] + b
            if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny] and place[nx][ny] != "X":
                visited[nx][ny] = True
                queue.append([nx, ny, dist + 1])
                if place[nx][ny] == "P":
                    candidate.append(dist + 1)
    
    return True if candidate and min(candidate) <= 2 else False
                

def check_distance(place):
    for i in range(5):
        for j in range(5):
            if place[i][j] == "P":
                if bfs([i, j], place):
                    return 0
    return 1
                

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

 

 

🤔 문제 풀이

 

전체 2차원 배열의 가로 세로의 길이가 5밖에 되지 않으니, 모든 사람에 대해서 맨해튼 거리가 2 이하인 주변사람이 있는지 계산해주면 됩니다.

 

주변사람의 거리는 BFS로 풀이했습니다.

상하좌우 방향으로 범위를 초과하지 않고, 아직 방문하지 않은 지역이며, 플레이트로 막히지 않은 부분에 대해서 방문을 하고,

"O"처럼 빈 테이블이면 그냥 지나가고, "P"로 사람을 만났다면, 거리를 저장합니다.

 

모든 while문이 끝나면, candidate 배열에는 시작 지점으로부터 모든 사람과의 거리가 저장되어있고, 이 중 최소값을 기준으로 2이하라면 거리두기를 지키지 않은 것으로 로직을 설계했습니다.