백준(Python) 풀이/구현

백준(Python) 15683번 감시 풀이

개발윗미 2022. 4. 1. 12:47

Python으로 구현한 15683번 감시 문제 풀이입니다.

 

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

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net


import copy

n, m = map(int, input().split())
office = []
cctv = []

case = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]]
]

# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def dfs(depth, arr) :
    global result
    if depth == len(cctv) :
        count = 0
        for i in range(n) :
            count += arr[i].count(0)
        result = min(result, count)
        return

    temp = copy.deepcopy(arr)
    cctv_num, x, y = cctv[depth]
    for i in case[cctv_num] :
        fill(temp, i, x, y)
        dfs(depth + 1, temp)
        temp = copy.deepcopy(arr)


def fill(board, index, x, y) :
    for i in index :
        nx = x
        ny = y
        while True :
            nx += dx[i]
            ny += dy[i]
            if not 0 <= nx < n or not 0 <= ny < m :
                break
            if board[nx][ny] == 6 :
                break
            elif board[nx][ny] == 0 :
                board[nx][ny] = 7

for i in range(n) :
    data = list(map(int, input().split()))
    office.append(data)
    for j in range(m) :
        if data[j] in [1, 2, 3, 4, 5] :
            cctv.append([data[j], i, j]) # [cctv 번호, 좌표]

result = int(1e9)
dfs(0, office)
print(result)

 

1. 5가지 종류의 CCTV가 각각 감시할 수 있는 방법을 3차원 리스트 형태로 구성하여 case에 정의한다.

 

2. CCTV를 90도 방향으로 회전할 수 있으므로 북쪽, 동쪽, 남쪽, 서쪽 방향을 dx, dy 리스트에 정의한다.

 

3. 사무실 각 칸의 정보를 한 줄씩 입력받고, 그 줄의 각 요소를 확인하여 그 값이 CCTV번호라면 cctv 리스트에 [CCTV 번호, 좌표] 형태로 추가한다.

 

4. dfs() 함수를 통해 해당 CCTV의 방향들을 감시하고, CCTV 개수만큼 감시를 완료하면 사각지대의 최솟값을 갱신한 후 return 한다.

 

5. fill() 함수를 통해 해당 CCTV의 방향에 따라 감시할 수 있는 칸은 7로 갱신시키고, 벽을 만나거나 범위를 초과하면 감시를 종료한다.