거리두기 확인하기

• 그냥 구현문제..
• 모든 셀에 대해서 그 셀에 응시자가 있는 경우, 맨해튼 거리 2 이내의 셀중에 거리두기를 안지킨 응시자가 있는지 확인하면 된다. BFS로 구현할수도 있지만, 그냥 상하좌우로 인접한 셀, 대각선으로 인접한 셀, 상하좌우로 2칸 거리의 셀의 세가지 패턴으로 나누어서 응시자가 있고 파티션이 없는 경우가 있는지를 각각 확인하는 것이 좀더 편리하다.
  • 만약 문제 조건이 맨해튼거리 3이내였다면 BFS로 하는게 편할것이다..
• 맨해튼 거리 2 이내의 셀의 개수는 상수이므로.. 각 셀에 대해서 거리두기가 지켜지는 지를 찾는것도 O(1)이다. 총 시간복잡도는 O(|셀의 개수|)이지만.. 셀의 개수도 5×5로 고정되어 있으므로 그냥 O(1)이라고 생각해도 되긴 한다.

"""Solution code for "Programmers 81302. 거리두기 확인하기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/81302
- Solution link: http://www.teferi.net/ps/problems/programmers/81302
"""

DELTA = ((1, 0), (0, 1), (-1, 0), (0, -1))


def is_okay(place):
    def is_person_at_pos(r, c):
        return 0 <= r < 5 and 0 <= c < 5 and place[r][c] == 'P'
    
    for r in range(5):
        for c in range(5):
            if not is_person_at_pos(r, c):
                continue
            for (dr1, dc1), (dr2, dc2) in zip(DELTA, DELTA[1:] + DELTA[:1]):
                nr, nc = r + dr1, c + dc1
                nnr, nnc = r + dr1 + dr1, c + dc1 + dc1
                nr2, nc2 = r + dr2, c + dc2
                diag_r, diag_c = r + dr1 + dr2, c + dc1 + dc2
                if is_person_at_pos(nr, nc):
                    return False
                if is_person_at_pos(nnr, nnc) and place[nr][nc] != 'X':
                    return False
                if (is_person_at_pos(diag_r, diag_c) and 
                        (place[nr][nc] != 'X' or place[nr2][nc2] != 'X')):
                    return False            
    return True


def solution(places):
    return [1 if is_okay(x) else 0 for x in places]