[구현] 15683 감시

조은지·2022년 2월 11일

링크 - https://www.acmicpc.net/problem/15683

코드 1

#감시 22-02-11
from collections import deque
import sys
input = sys.stdin.readline
dx=[-1,1,0,0] #상하좌우
dy=[0,0,-1,1]
#cctv번호 별 탐색방향
directions=[[],
            [[0],[1],[2],[3]],
            [[0,1],[2,3]],
            [[0,3],[1,3],[1,2],[0,2]],
            [[0,2,3],[1,2,3],[0,1,2],[0,1,3]],
            [[0,1,2,3]]]

answer=int(1e9)

#0의 개수를 세어주는 함수
def counting_zero():
    count=0
    for i in range(n):
        for j in range(m):
            if graph[i][j]==0:
                count+=1
    return count
    
#cctv 완전탐색 (DFS로 cctv 완전탐색을 실행한다.)
def monitoring(index):
    global answer;
    if index==cctv_num: #끝까지 탐색한 경우
        answer = min(answer,counting_zero()) #최솟값을 갱신한다.
        return

    sx,sy,number = cctv[index][0],cctv[index][1],cctv[index][2] #탐색할 cctv의 위치와 번호
    direction=directions[number] #해당 cctv가 탐색하는 방향 선택

    for d in direction: #탐색 가능한 방향 리스트
        q = deque()
        for i in d: #리스트 중 하나 탐색
            x = sx #시작점을 cctv위치로 초기화
            y = sy
            while True:
                x+=dx[i]
                y+=dy[i]
                if 0<=x<n and 0<=y<m: #범위 내에 들고
                    if graph[x][y]==0: #0이면 탐색
                        graph[x][y]='#'
                        q.append((x,y))
                    elif graph[x][y]==6:#벽이면 탐색 중지
                        break
                else: #범위를 넘어가면 탐색 중지
                    break
        monitoring(index+1) #다음 cctv 탐색
        while q:
            x, y = q.popleft()
            graph[x][y] = 0  # 탐색한 표시 원상복귀


n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
cctv=[]
#cctv 찾기
for i in range(n):
    for j in range(m):
        if graph[i][j]!=0 and graph[i][j]!=6:
            cctv.append((i,j,graph[i][j])) #cctv위치, cctv번호

cctv_num=len(cctv) #cctv 개수
monitoring(0)
print(answer)

코드2 (시간 줄임)

# 감시 22-02-11
from collections import deque
import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]  # 상하좌우
dy = [0, 0, -1, 1]
# cctv번호 별 탐색방향
directions = [[],
              [[0], [1], [2], [3]],
              [[0, 1], [2, 3]],
              [[0, 3], [1, 3], [1, 2], [0, 2]],
              [[0, 2, 3], [1, 2, 3], [0, 1, 2], [0, 1, 3]],
              [[0, 1, 2, 3]]]

answer = 0
tmp=0
# cctv 완전탐색 (재귀로 cctv 완전탐색을 실행한다.)
def monitoring(index):
    global answer;
    global tmp;
    if index == cctv_num:
        answer=max(answer,tmp)
        return
    sx, sy, number = cctv[index][0], cctv[index][1], cctv[index][2]
    direction = directions[number]  # cctv 번호 선택

    for d in direction:  # 탐색 가능한 방향 리스트
        q = deque()
        for i in d:  # 한 방향 탐색
            x = sx
            y = sy
            while True:
                x += dx[i]
                y += dy[i]
                if 0 <= x < n and 0 <= y < m:  # 범위 내에 들고
                    if graph[x][y] == 0:  # 0이면 탐색
                        graph[x][y] = '#'
                        q.append((x, y))
                        tmp+=1 #탐색 개수 추가
                    elif graph[x][y] == 6:  # 벽이면 탐색 중지
                        break
                else:
                    break
        monitoring(index + 1)
        tmp-=len(q) #tmp 개수 빼주기
        while q:
            x, y = q.popleft()
            graph[x][y] = 0  # 원상복귀


n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
cctv = []
total=0
# cctv 찾기
for i in range(n):
    for j in range(m):
        if graph[i][j] != 0 and graph[i][j] != 6:
            cctv.append((i, j, graph[i][j]))  # cctv위치, cctv번호
        if graph[i][j]==0:
            total+=1

cctv_num = len(cctv)  # cctv 개수
monitoring(0)
print(total-answer) #전체에서 탐색한 수 빼준다.

풀이 방법

DFS방식으로 가장 많이 탐색한 경우를 찾았다.
1. 각 cctv 별 탐색하는 방향을 directions 리스트에 미리 담아준다. (이 때, 인덱스 주의!)
2. cctv의 위치와 번호를 cctv 리스트에 저장
3. monitoring 함수로 dfs구현

**monitoring 함수에서 주의할 점!!**

1. 해당 cctv가 탐색할 수 있는 경우의 수 중 한가지를 먼저 탐색한 후 다음 cctv를 탐색하도록 호출
2. 탐색할 때 while True를 통해서 벽을 만나기 전까지 탐색하도록 한다. 
3. 큐에 방문한 위치를 담아서 원상복귀를 시켜야 한다.