[백준] 감시

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

15683번: 감시

DFS를 통한 구현 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

다음 그림과 같이 4방향을 감시할 수 있는 cctv들이 놓여있는 방이 있습니다. 이 방에는 벽이 있고, 만약 벽이 있다면, cctv는 벽 뒷편은 보지 못합니다. 이 때, cctv의 사각지대를 최소화 시키는 것이 문제입니다.

 

실제로 문제가 조금 기니 한번 읽어보는 것을 권장합니다.

 

<Solution>

DFS를 통해 각각의 cctv에 대해 가능한 방향을 조회하도록 구현을 하면 됩니다. DFS를 사용하지 않으면, 저장해야 하는 그래프의 상태가 너무 많아지기 때문에 DFS로 각각에 마킹을 하고, 다시 해제하는 형태가 가장 적합할 것임을 예상 할 수 있습니다.

 

실제 구현은 아래와 같습니다. (중복되는 부분들이 많은데 구성 성분들을 다르게 쪼개서 좀더 깔끔하게 짜는 것이 좋아 보이기는 합니다.)

import sys
import copy
N, M  = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

cctv = []
blind_spot = 0
for r in range(N):
    for c in range(M):
        if 1 <= graph[r][c] <= 5:
            cctv.append((r,c))
        elif graph[r][c] == 0:
            blind_spot += 1

dir_r = [0, 0, -1, 1] # left rigt up down
dir_c = [-1, 1, 0, 0]

# dfs
ans = int(2e9)
def dfs(index, blind_spot):
    global ans
    global graph
    if index == len(cctv):
        ans = min(ans, blind_spot)
        return
    r, c = cctv[index]
    if graph[r][c] == 1:
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, False, False, False, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, True, False, False, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, False, True, False, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, False, False, True, blind_spot))
        graph = graph_

    if graph[r][c] == 2:
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, True, False, False, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, False, True, True, blind_spot))
        graph = graph_

    if graph[r][c] == 3:
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, False, True, False, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, False, False, True, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, True, False, True, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, True, True, False, blind_spot))
        graph = graph_

    if graph[r][c] == 4:
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, False, True, True, True, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, False, True, True, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, True, False, True, blind_spot))
        graph = graph_
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, True, True, False, blind_spot))
        graph = graph_

    if graph[r][c] == 5:
        graph_ = copy.deepcopy(graph)
        dfs(index + 1, fill(graph, r, c, True, True, True, True, blind_spot))
        graph = graph_

def fill(graph, r, c, dir1, dir2, dir3, dir4, blind_spot): # left right up down
    mem_r, mem_c = r,c
    if dir1 == True:
        while(1):
            r += dir_r[0]
            c += dir_c[0]
            if r < 0 or r >= N or c < 0 or c >= M or graph[r][c] == 6: 
                break
            if graph[r][c] == 0:
                blind_spot -= 1
                graph[r][c] = '#'

    r, c = mem_r, mem_c
    if dir2 == True:
        while(1):
            r += dir_r[1]
            c += dir_c[1]
            if r < 0 or r >= N or c < 0 or c >= M or graph[r][c] == 6: 
                break
            if graph[r][c] == 0:
                blind_spot -= 1
                graph[r][c] = '#'
    r, c = mem_r, mem_c
    if dir3 == True:
        while(1):
            r += dir_r[2]
            c += dir_c[2]
            if r < 0 or r >= N or c < 0 or c >= M or graph[r][c] == 6: 
                break
            if graph[r][c] == 0:
                blind_spot -= 1
                graph[r][c] = '#'
    r, c = mem_r, mem_c
    if dir4 == True:
        while(1):
            r += dir_r[3]
            c += dir_c[3]
            if r < 0 or r >= N or c < 0 or c >= M or graph[r][c] == 6: 
                break
            if graph[r][c] == 0:
                blind_spot -= 1
                graph[r][c] = '#'
    return blind_spot

dfs(0, blind_spot)

print(ans)