[백준 15683번] 감시(파이썬)

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

15683번: 감시

이 문제는

dfs를 통한 백트레킹

cctv구현

이 두가지를 해야해서

체감 난이도는 높았습니다.

 

우선, 난감해보이는

cctv구현.

보통 저렇게 모드가 여러가지가 있다면

한 리스트에

모든 cctv를 구현해줍니다.

저같은 경우에는

 

mode=[[],
  [[1],[2],[3],[4]],
  [[1,3],[2,4]],
  [[1,2],[2,3],[3,4],[4,1]],
  [[1,2,3],[1,2,4],[2,3,4],[1,3,4]],
  [[1,2,3,4]],
  ]

 

이렇게 cctv각각의 mode를 구했습니다.

 

그 후, cctv의 좌표를 받아야하는데요

for문 돌려서 하나씩 일일이 받을수도 있지만

그러기에는 시간이 너무 오래걸립니다.

 

N,M=map(int,input().split())
cctv=[]
room=[]

for i in range(N):
  data=list(map(int,input().split()))
  room.append(data)
  for j in range(M):
    if data[j] in [1,2,3,4,5]:
      cctv.append([data[j],i,j])

 

이 부분은 검색해보니

이런식으로 나오더군요.

저렇게 하면서

cctv안에

모드와 좌표가

동시에 담기는 개념입니다.

 

그 다음에는 감시를 해야겠죠?

cctv를 기준으로

저렇게 예시를 구상해봤습니다.

현재 cctv가 있는 좌표를 기준으로

감시구역을 계속 보고가되

벽을 만난다거나, 범위를 벗어나면 break한다

라는 느낌으로 갔습니다.

 

그리고 백트래킹.

각각 cctv가 구하는 감시의 모든 케이스를 구하는 겁니다.

문제에 주어진

예시 3의 케이스를 보면

이해를 더 알 수 있습니다.

케이스를 그려보면

무수한 케이스가 등장합니다.

첫번째 1이 왼쪽을 볼 떄

두번째 1는 위를 볼 수 있고

그 때 세번째 1은 아래를 볼 수 있고....

결국, 이를 위해서 백트레킹을 해줘야합니다.

이를 위해,deepcopy를 써줬습니다.

 

 

직접 코드를 보겠습니다.

 

# 백준 15683감시
import copy

N, M = map(int, input().split())
cctv = []
room = []
for i in range(N):
    data = list(map(int, input().split()))
    room.append(data)
    for j in range(M):
        if data[j] in [1, 2, 3, 4, 5]:
            cctv.append([data[j], i, j])
c_num = len(cctv)

dx = [0, 0, -1, 0, 1]
dy = [0, 1, 0, -1, 0]

# cctv각각에 방향별로 저장
mode = [[],
        [[1], [2], [3], [4]],
        [[1, 3], [2, 4]],
        [[1, 2], [2, 3], [3, 4], [4, 1]],
        [[1, 2, 3], [1, 2, 4], [2, 3, 4], [1, 3, 4]],
        [[1, 2, 3, 4]],
        ]
min_not = 1e9


# cctv 감시방향 설정
def search(room, x, y, see):
    for look in see:
        nx = x
        ny = y
        while True:
            nx = nx + dx[look]
            ny = ny + dy[look]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                break
            if room[nx][ny] == 6:
                break
            room[nx][ny] = 7


# 사각지대 확인법
def not_see():
    global min_not
    tmp_not = 0
    for x in range(N):
        for y in range(M):
            if room[x][y] == 0:
                tmp_not += 1
    min_not = min(min_not, tmp_not)
    # print(room)


# 각각 cctv가 보는 모든 케이스를 구하고, 사각지대 백트래킹
def dfs(depth):
    global c_num
    global room
    if depth == c_num:
        # 감시구역 구하는 함수 넣고
        not_see()
        return

    m = cctv[depth][0]
    now_mode = mode[m]
    n_x, n_y = cctv[depth][1], cctv[depth][2]
    tmp_room = copy.deepcopy(room)
    for see in range(len(now_mode)):
        # 감시구역 구하는 함수 넣기
        search(room, n_x, n_y, now_mode[see])
        dfs(depth + 1)
        room = copy.deepcopy(tmp_room)


dfs(0)
print(min_not)

 

백트레킹개념은 처음에 상당히 어렵게 느껴지는 개념입니다.

솔직히 몇번 본다고 받아드리기 쉬운 개념은 아닙니다.

직접 코드를 쳐보면서

머릿속으로 그려보는 걸 추천드립니다.

저는 이 문제를 풀다가

2%대에서 틀렸습니다가 뜨길래

다시 보니, 모드4를 잘못구현했더군요.

저런 구현을 구할 때

노트에다가 적어가면서

혹시 내가 틀린 건 없는지

체크하는 습관을 들여야겠습니다.

또, 내가 구하고 싶은 좌표(여기서는 cctv좌표)를 구할 때

어떻게 리스트에 받을지도

생각할 수 있었던 문제였습니다.

 

(내용추가-2022.10.12)

from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

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

N,M=map(int,input().split())

room=[]
tv=[]
all=[]
def dfs(depth):
    global answer,watch
    if depth==t_len:
        ha=0
        for x in range(N):
            ha+=watch[x].count(0)

        answer=min(answer,ha)
        return
    tx,ty,num=tv[depth]
    now_scan=scan[num]
    temp=deepcopy(watch)
    for case in now_scan:
        for do in case:
            nx=tx
            ny=ty
            while True:
                nx += dx[do]
                ny += dy[do]
                if not inside(nx, ny):
                    break
                if room[nx][ny] == 6:
                    break
                watch[nx][ny] = 1

        dfs(depth+1)
        watch=deepcopy(temp)

def inside(x,y):
    if x<0 or x>=N or y<0 or y>=M:
        return False

    return True



watch=[[0]*M for _ in range(N)]
for i in range(N):
    tmp=list(map(int,input().split()))
    room.append(tmp)
    for j in range(M):
        if 1<=tmp[j]<=4:
            tv.append((i,j,tmp[j]-1))
            watch[i][j]=1
        elif tmp[j]==5:
            all.append((i,j))
            watch[i][j]=1
        elif tmp[j]==6:
            watch[i][j]=1
t_len=len(tv)

answer=1e9


#먼저, 전방위로 스캔하는 거 먼저.
#탐색 최소화

for x,y in all:
    for d in range(4):
        nx=x
        ny=y

        while True:
            nx+=dx[d]
            ny+=dy[d]
            if not inside(nx,ny):
                break
            if room[nx][ny]==6:
                break
            watch[nx][ny]=1


dfs(0)
print(answer)

 

다시 풀 때는 시간을 어떻게 더 줄일까 고민해봤는데

먼저 5에 해당하는

상하좌우 다 보는 걸 먼저 돌려주는 걸로 했습니다.

이 문제에서 백트레킹을 쓰는 건

각각 방향별로 케이스가 다르기 떄문에 해주는 건데

5는 항상 전방향이니깐 굳이 그럴 필요가 없습니다.

만약 백트레킹에 넣는다면

굳이 시간만 더 잡아먹는 느낌.

그래서 백트레킹으로 구하기 전에

먼저 전방향 카메라 먼저 구해놓고 구했습니다.

 

(근데 문제 불친절맨인게...

CCTV랑 벽있는 것도 사각지대에 치는지 안치는지

예제를 봐야 이해가 된다 맨이야)