[Python] 백준 BOJ 15683 - 감시

cctv가 볼 수 있는 방향이 정해져 있고, 그 방향은 회전할 수 있다. 따라서 하나의 cctv당 최대 4가지의 경우의 수가 생성되며, cctv의 개수는 총 5개이다. 

 

2차원 배열에서 사각지대를 최소화하는 cctv의 방향을 선택하여 배치하는 문제였다. 가능한 경우의 수가 다양하기에 탐색 알고리즘보다는 경우의 수를 구현할 때 반복문이 겹쳐지지 않게 실수하지 않을 것과 어떻게 정형화하여 표현하는가에 대해 집중하였다.

 

백준 문제집: 삼성 SW 역량 테스트 기출문제

>> https://www.acmicpc.net/workbook/view/1152

감시 (난이도: 골드 Ⅲ)

>> https://www.acmicpc.net/problem/15683

---

작성코드

import copy

#cctv가 볼 수 있는 범위를 체크하는 함수
def look(mapp, directions, x, y):
    for d in directions: #directions에는 각 카메라가 볼 수 있는 방향들이 저장되어 있음
        nx = x
        ny = y
        while True:
            nx += dir[d][0] #newx
            ny += dir[d][1] #newy

            if nx < 0 or nx >= N or ny < 0 or ny >= M or mapp[nx][ny] == 6: #맵 밖이거나 벽을 만나는 경우
                break
            elif mapp[nx][ny] == 0:
                mapp[nx][ny] = -1 #-1로 시야체크

#dfs 함수. 예외처리는 따로 하지 않아 브루트포스 알고리즘을 사용함 
def dfs(depth, mapp):
    global min_value #dfs가 재귀적으로 돌아가므로 함수 외부의 변수를 이용하여 최솟값을 갱신한다.
    
    if depth == len(cams): #dfs 한세트가 끝난 경우
        temp = sum(row.count(0) for row in mapp) #0개수 세기(0은 사각지대를 의미)
        min_value = min(min_value, temp) #최솟값갱신
        return
    
    x, y, cam_num = cams[depth]  

    for curr_dir in directions[cam_num]: #현재 카메라 번호에 따라 방향이 달라짐
        temp_map = copy.deepcopy(mapp) #보드 초기화
        look(temp_map, curr_dir, x, y)
        dfs(depth + 1, temp_map) #재귀

def main():
    global N, M, dir, directions, cams, min_value
    N, M = map(int, input().split())
    mapp, cams = [], []

    for i in range(N):
        row = list(map(int, input().split()))
        for j in range(M):
            if row[j] in {1, 2, 3, 4, 5}: #cctv에 해당하는 경우
                cams.append((i, j, row[j])) #열, 행, 카메라번호
                row[j] = -1 #cctv가 자리잡고있는 위치는 시야가 확보된 것으로 판단(문제설명)
        mapp.append(row)

    dir = [(-1, 0), (0, 1), (1, 0), (0, -1)] #상 우 하 좌

    directions = {1: [[0], [1], [2], [3]],                          #상/우/하/좌
                  2: [[0, 2], [1, 3]],                              #상하/좌우
                  3: [[0, 1], [1, 2], [2, 3], [3, 0]],              #상우/우하/하좌/좌상
                  4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],  #상우하/우하좌/하좌상/좌상우
                  5: [[0, 1, 2, 3]]}                                #상하좌우

    min_value = float('inf')

    dfs(0, mapp)
    print(min_value)

if __name__ == '__main__':
    main()

 

코드는 카메라가 방향별로 배치 되었을 때의 사각지대의 갯수를 모두 계산한다. 깊이 우선 탐색(DFS) 알고리즘을 사용하였으며, 이를 재귀적으로 구현하였다. depth 변수는 탐색의 깊이를 저장하고, 한세트가 끝났음을 알림으로서 재귀함수의 종료 조건이 된다. 

 

cctv의 종류에 따라 바라볼 수 있는 방향의 조합이 달라지는데, 우선 "상 우 하 좌" 방향은 dir 배열을 통해 표현하였다. 이후 딕셔너리를 이용하여 가능한 방향의 조합을 표현하였다. 이때 딕셔너리의 value값은 리스트이며, 리스트의 원소는 dir의 인덱스로 표현된 방향이 리스트로 저장되어있다.

 

...

dir = [(-1, 0), (0, 1), (1, 0), (0, -1)] #상 우 하 좌

    directions = {1: [[0], [1], [2], [3]],                          #상/우/하/좌
                  2: [[0, 2], [1, 3]],                              #상하/좌우
                  3: [[0, 1], [1, 2], [2, 3], [3, 0]],              #상우/우하/하좌/좌상
                  4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],  #상우하/우하좌/하좌상/좌상우
                  5: [[0, 1, 2, 3]]}                                #상하좌우
                  
...

 

이 때 리스트로 저장해둔 이유는 2중 for문을 이용하여 카메라의 방향 조합을 표현해야 하기 때문이다.  

코드를 보면, look함수는 dfs함수의 for문 내에 있는데, look함수 또한 for문을 수행하기 때문에 코드는 2중 for문을 수행하고 있다고 볼 수 있다.

2번 cctv를 예시로 들어보겠다. 2번 cctv는 상우/우하/하좌/좌상의 방향 조합을 가질 수 있다. dfs함수는 2번 cctv가 가질 수 있는 조합을 모두 실행하게 한다(재귀이용). 2번 cctv가 "상우" 조합을 가지게 된 경우라면 look함수에서는 for문을 이용하여 "상"과 "우"인 경우의 각각 cctv의 시야를 체크한다. 따라서 directions의 value값은 2차원 리스트인 것이다.

 

directions를 3차원 리스트로 구현하는 것도 가능하지만, 리스트의 인덱스는 0부터 시작이므로 cctv의 번호를 그대로 이용하지 못한다. 연산을 최소화하고 좀 더 직관적인 코드를 위해 딕셔너리를 구현하였다. 참고로 딕셔너리 자료구조는 리스트에 비해 메모리 사용량을 늘어나지만 검색/삭제/수정 시간이 빠르다. 이는 딕셔너리가 해시 테이블을 사용하여 키를 검색하기 때문이다.