[BOJ] 15683. 감시

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

15683번: 감시

 

 

1. 해결방법

이 문제는 시뮬레이션 문제이다. 
주어진 상황을 차례로 코드로 구현시키면 되고 모든 경우를 찾아봐야 하므로 완전탐색 dfs 재귀를 사용해야 한다.

본인은 생각하지 못한 점인데 direction 각 cctv의 방향을 미리 리스트화 시키는 것이다. 그리고 dy, dx를 통해서 그래프의 상하좌우를 정해준다.
direction에 원소 값들과 인덱스 위치 값을 stack에 append 하고 stack의 길이가 cctv_list의 길이와 같아진다면 cctv의 모든 방향을 탐색하는 작업을 하면 된다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline
from copy import deepcopy

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


# check
def check(copy_maps, element, y, x):
    for direct in element:
        ny, nx = y + dy[direct], x + dx[direct]

        while 0 <= ny < N and 0 <= nx < M:
            if copy_maps[ny][nx] == 0:
                copy_maps[ny][nx] = -1
                ny += dy[direct]
                nx += dx[direct]
            elif 1 <= copy_maps[ny][nx] < 6 or copy_maps[ny][nx] == -1:
                ny += dy[direct]
                nx += dx[direct]
            elif copy_maps[ny][nx] == 6:
                break


# dfs
def dfs(stack, idx):
    global answer

    # 종료
    if len(stack) == len(cctv_list):
        copy_maps = deepcopy(maps)
        
        # cctv 감시 지점 체크
        for element, y, x in stack:
            check(copy_maps, element, y, x)

        # 그래프의 합
        total = 0
        for i in range(N):
            for j in range(M):
                if copy_maps[i][j] == 0:
                    total += 1
        answer = min(answer, total)
        return

    cctv, y, x = cctv_list[idx]

    if cctv == 1:
        direction = [[0], [1], [2], [3]]
    elif cctv == 2:
        direction = [[0, 2], [1, 3]]
    elif cctv == 3:
        direction = [[0, 1], [1, 2], [2, 3], [3, 0]]
    elif cctv == 4:
        direction = [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]]
    else:
        direction = [[0, 1, 2, 3]]

    for element in direction:
        stack.append((element, y, x))
        dfs(stack, idx + 1)
        stack.pop()


# main
cctv_list = []
for i in range(N):
    for j in range(M):
        if maps[i][j] != 0 and maps[i][j] != 6:
            cctv_list.append((maps[i][j], i, j))

dy, dx = (-1, 0, 1, 0), (0, 1, 0, -1)
answer = 1e9
dfs([], 0)
print(answer)