문제

프로그래머스 카카오 거리두기 확인하기

정답 코드

from collections import deque
dxs, dys = (1, -1, 0, 0), (0, 0, 1, -1)


def solution(places):
    answer = []
    for place in places:
        is_success = True
        participants = []
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    participants.append([j, i])
        dq = deque()
        for j, i in participants:
            dq.appendleft((j, i, 0))
            visited = [[False for _ in range(5)] for __ in range(5)]
            visited[i][j] = True
            while dq:
                x, y, dis = dq.pop()
                for dx, dy in zip(dxs, dys):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < 5 and 0 <= ny < 5 and not visited[ny][nx]:
                        if place[ny][nx] == 'O':
                            dq.appendleft((nx, ny, dis + 1))
                            visited[ny][nx] = True
                        elif place[ny][nx] == 'P':
                            if dis + 1 <= 2:
                                is_success = False
        answer.append(1 if is_success else 0)
    return answer

풀이

완전탐색 BFS 문제입니다!
여러 개의 대기실을 보면서 각 대기실에 응시자들이 거리두기를 잘 지켰는지 확인하면 되는 간단한 문제입니다.

우선 저는 대기실을 탐색해서 응시자들의 위치를 participants 라는 배열에 저장했습니다.

이제 participant 배열에서 하나씩 응시자를 꺼내서 각각 다른 응시자와의 거리를 BFS로 측정했습니다.
그리고 각각 응시자마다 BFS를 위한 visited 배열을 사용했습니다.

여기서 이제 분기가 나뉘는데요
만약 진행하고자 하는 다음 위치에 있는 것이
1. 그냥 빈 공간일 경우 - 그냥 전진합니다
2. 다른 응시자가 있을 경우
1. 거리 + 1(다음에 방문할 공간이라서)이 2 이하인 경우 - 실패이므로 flag 값 변경
2. 거리 + 1이 2 초과인경우 - 거리두기를 잘 지켰으므로 flag 값 변경 안함

의문점

처음에는 이렇게 무식(?) 하게 돌아도 되나.... 생각을 좀 했는데,
1. 대기실은 5x5 크기로 고정되어있고,
2. 이러한 대기실이 5개 들어오며
3. 효율성 검사가 없는 문제
라는 3가지 이유로 완전 탐색을 진행해서 해결했습니다.