[python] 백준 15683 - 감시

출처 : 백준, https://www.acmicpc.net/problem/15683

15683번: 감시

    # 1번 1방향            
    # 2번 서로 반대 방향    
    # 3번 서로 직각       
    # 4번 3방향           
    # 5번 4방향           
    # CCTV는 벽을 넘을 수 없으나, CCTV는 넘을 수 있다.

    # 최소 사각지대의 개수

 

 

먼저, 생각해야 할 부분

 

1. 여러개의 CCTV가 바라볼 수 있는 모든 방향에 대한 조합을 어떻게 구할지 생각해본다.

 

---

 

풀이

 

5번, 2번, 1번 카메라가 있을 때 DFS를 이용한 최솟값 갱신

 

모든 조합을 훑어 최소값을 알아보고 싶다면,

깊이 우선 탐색을 이용해 모든 CCTV의 방향을 살펴보고 모든 CCTV에 대해 살펴보았을 때 최솟값을 갱신 후

가장 마지막에 살펴본 CCTV의 방향을 바꾸어 다시 최솟값을 갱신하면 될 것이다.

이는 DFS를 통해 구현할 수 있다.

 

from collections import defaultdict

EMPTY = 0
WALL = 6
VIEWED = '#'

viewed_area = 0
min_val = float('inf')

def calcUnlookCCTVArea(office, cctv_list, total_empty):
    cctv_type = dict([
        [1, [[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]]],
        [2, [[(0, 1), (0, -1)], [(1, 0), (-1, 0)]]],
        [3, [[(0, -1), (-1, 0)], [(-1, 0), (0, 1)], [(0, 1), (1, 0)], [(1, 0), (0, -1)]]],
        [4, [[(0, -1), (-1, 0), (0, 1)], [(-1, 0), (0, 1), (1, 0)], [(0, 1), (1, 0), (0, -1)],
             [(1, 0), (0, -1), (-1, 0)]]],
        [5, [[(0, 1), (0, -1), (1, 0), (-1, 0)]]]])

    N = len(office)
    M = len(office[0])

    def recursiveDFS(office, cctv_list):
        global viewed_area
        global min_val

        if len(cctv_list) == 0: #최솟값 갱신
            min_val = min(min_val, total_empty - viewed_area)

            return

        # cctv 리스트 중 0번째를 가져온다. 
        point, type = cctv_list[0]
        cctv_r, cctv_c = point

        # 하나의 바라보는 방향을 선택
        for dir_list in cctv_type[type]:
            change_list = []
            # 시야 채워넣기
            for dr, dc in dir_list:
                nr = cctv_r + dr
                nc = cctv_c + dc

                # 범위 밖으로 나가거나 벽에 닿을 때까지
                while 0 <= nr < N and 0 <= nc < M and office[nr][nc] != WALL:
                    if office[nr][nc] == EMPTY: #EMPTY 칸이라면
                        office[nr][nc] = VIEWED # 시야 표시
                        change_list.append((nr, nc)) # 변경한 칸 추가
                        viewed_area += 1

                    # 위치 이동
                    nr += dr
                    nc += dc

            # 0번째 성분을 제외하고 재귀
            recursiveDFS(office, cctv_list[1:])
			
            # 변경한 칸 원상 복구
            for change_r, change_c in change_list:
                office[change_r][change_c] = 0

            viewed_area -= len(change_list)

    recursiveDFS(office, cctv_list)

    return min_val
    
def solution(N, M, office):
    total_empty = 0

    cctv_list = defaultdict(lambda : [])

    # cctv 모두 찾기, 빈 칸 개수 계산
    for i in range(N):
        for j in range(M):
            if office[i][j] == WALL:
                continue

            if office[i][j] == EMPTY:
                total_empty += 1
                continue

            cctv_list[(i, j)] = office[i][j]

    return calcUnlookCCTVArea(office, list(cctv_list.items()), total_empty)

N, M = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(N)]

print(solution(N, M, office))

 

---

알게 된 점

 

파이썬의 중첩함수

def outerFunction():
    sayHi = 'hello World'
    
    def innerFunction():
        print(sayHi)    # hello World

파이썬 역시 함수 내부에 함수를 작성하는 중첩함수가 가능하다.

단, 외부 함수의 변수를 내부 함수에서 참조할 수는 있지만, 변경할 경우 재할당되어 별도의 변수가 되어버린다.

즉, 내부 함수에서 변경된 값은 외부 함수의 변수에 영향을 미치지 않는다.

 

따라서 내부 함수에서 외부함수의 변수를 사용하고자 할 경우,

 

1. 참조만 할 수 있다.

2. 변경하고 싶다면, 외부 함수의 변수를 global로 빼고 내부함수에서 global 변수 선언 후 재할당 할 수 있다.

 

좌표 입력이 잦은 경우에 상수를 선언하는게 편하다.

NORTH = (-1, 0)
SOUTH = (1, 0)
EAST = (0, -1)
WEST = (0, 1)

 

이 문제와 같이 좌표 입력이 잦은 경우에는 상수로 선언해두는게 편하다.

생각보다 오타가 자주 나는 부분 중 하나라서 다음부터는 상수로 선언해두자.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들