설명

[ 문제 비공개 ]

풀이

def solution(places):
    # fixed 5 * 5. 
    # P: applier
    # O: empty table
    # X: partition
    
    answer = [1] * len(places)
    
    def check_social_distancing(room_index, current_node_coordinate, visited_node_coordinates, distance):
        # current_node_coordinate = (i, j). tuple
        # visited_node_coordinates = {(i, j), (m, n), ...}. set
        r, c = current_node_coordinate
        
        # outside of map
        if r >= 5 or r < 0 or c >= 5 or c < 0:
            return
        
        # safe social distance
        if distance > 2:
            return
        
        # cannot go further(blocked by partition).
        if places[room_index][r][c] == "X":
            return
        
        # already visited node.
        if current_node_coordinate in visited_node_coordinates:
            return
        
        visited_node_coordinates.add(current_node_coordinate)
        # not enough social distance.
        if len(visited_node_coordinates) > 1 and distance <= 2 and places[room_index][r][c] == "P":
            answer[room_index] = 0
            return

        check_social_distancing(room_index, (r-1, c), visited_node_coordinates, distance + 1)
        check_social_distancing(room_index, (r+1, c), visited_node_coordinates, distance + 1)
        check_social_distancing(room_index, (r, c-1), visited_node_coordinates, distance + 1)
        check_social_distancing(room_index, (r, c+1), visited_node_coordinates, distance + 1)
        
    
    for index, place in enumerate(places):
        # P에서 시작하여 O만 지나갈 때 이동거리 2 이하로 다른 P를 만난다면 실패.
        for r in range(5):
            for c in range(5):
                if place[r][c] == "P":
                    check_social_distancing(index, (r, c), set(), 0)
    
    return answer

문제에서 친절하게 맨해튼 거리라는 개념을 알려줬기 때문에 그래프 탐색 풀이를 생각할 수 있었다.