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

1. 요약

각 대기실에 있는 응시자가 거리두기를 잘 지키고 있는 지 알아보는 문제.
응시자간 사이의 거리를 맨해튼 거리로 정의하고 맨해튼 거리가 2이하이면 거리두기를 못 지켰다고 할 수 있다. 단, 맨해튼 거리가 2이하이더라도, 중간에 파티션이 존재하면 거리두기를 잘 지킨 것이다.

2. 아이디어

맨해튼 거리의 정의는 |y1-y2|+|x1-x2|이다.(맨해튼거리-위키백과 참고)
문제를 이해했다면, 아래와 같이 해석할 수 있다.

어떤 대기실에 있는 사람A가 있는 칸에서 출발하여, 인접한 칸에 대해 상하좌우로 움직이면서, 사람B가 있는 칸까지간다. 파티션이 있는 칸은 갈 수 없을 때, 사람B까지 도달하는 최단 거리를 구한다. 최단 거리가 2이하이면 거리두기를 지켰다고 할 수 없다.

따라서 각 사람들을 출발점으로 지정하고 BFS를 이용하여 다른 사람들까지의 맨해튼 거리를 구하고 거리두기를 지켰는지 확인하다.

필력이 좋은편은 아니라서, 더 깔끔한 해설은 2021 카카오 인턴십 코딩테스트 해설을 참고하길 바란다.

3. 코드

from collections import deque

d = ((0,1), (1,0), (-1,0), (0,-1))
SIZE = 5

def make_maps(place):
    arr = []
    men = []
    for i, string in enumerate(place):
        for j, ch in enumerate(string):
            if ch == 'P':men.append((i,j))

        arr.append(list(string))
    
    return arr, men

def isin(y,x):
    if -1<y<SIZE and -1<x<SIZE: return True
    return False

def bfs(arr, sy, sx):
    q = deque()
    q.append((sy, sx))
    table = [[-1 for _ in range(SIZE)] for _ in range(SIZE)]
    table[sy][sx] = 0

    while q:
        y, x = q.popleft()

        for dy, dx in d:
            ny = y + dy
            nx = x + dx

            if not isin(ny, nx): continue
            if arr[ny][nx] != 'X' and table[ny][nx] == -1:
                table[ny][nx] = table[y][x] + 1
                q.append((ny, nx))
    
    return table
                    
def solution(places):
    answer = []
    for place in places:
        arr, men = make_maps(place)
        ok = True

        for man in men:
            table = bfs(arr, man[0], man[1])
            for other_man in men:
                if man != other_man:
                    y = other_man[0]
                    x = other_man[1]
                    if -1 < table[y][x] <= 2:
                        ok = False
                        break
            
            if not ok: break
        
        if ok: answer.append(1)
        else: answer.append(0)
            
    return answer