문제 링크
https://www.acmicpc.net/problem/15683
🕒 Python 풀이시간: 50분
from itertools import product
from collections import deque
import copy
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
def see_cctv(board,num,dir,pos):
# print(cctv_dir_detail[num])
for i in cctv_dir_detail[num][dir]:
q=deque()
q.append(pos)
while q:
now=q.popleft()
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=m:
continue
if board[nx][ny]==6:
continue
q.append((nx,ny))
board[nx][ny]=-1
cctv_dir=[0,4,2,4,4,1]
dx=[0,0,-1,1]
dy=[-1,1,0,0]
cctv_dir_detail=[(0,),((0,),(1,),(2,),(3,)),((0,1),(2,3)),((0,2),(0,3),(1,2),(1,3)),((0,1,2),(0,1,3),(0,2,3),(1,2,3)),((0,1,2,3),)]
cctv_pos=dict()
for i in range(1,6):
cctv_pos[i]=[]
for i in range(n):
for j in range(m):
if 1<=board[i][j]<=5:
cctv_pos[board[i][j]].append((i,j))
answer=1e9
products_cctv=dict()
for i in range(1,6):
products_cctv[i]=list(product(range(cctv_dir[i]),repeat=len(cctv_pos[i])))
all_cases=list(product(products_cctv[1],products_cctv[2],products_cctv[3],products_cctv[4],products_cctv[5]))
for case in all_cases:
cnt=0
tmp_board=copy.deepcopy(board)
for i in range(len(case)):
for j in range(len(case[i])):
see_cctv(tmp_board,i+1,case[i][j],cctv_pos[i+1][j])
for i in range(n):
for j in range(m):
if tmp_board[i][j]==0:
cnt+=1
# print(cnt)
answer=min(cnt,answer)
print(answer)📹 CCTV 설치 경우의 수 구하기
cctv를 설치하는 모든 경우의 수를 구하는 문제이다. 각 cctv에 부여되는 방향도 전부 제 각각이고 종류도 전부 다르기 때문에 가짓수를 구하는 문제 중에서 까다로운 편이라고 할 수 있다.
먼저 각 종류의 cctv를 위치를 저장한다. 차후, 위치에 따라 부여된 방향과 종류로 탐색을 진행해야하기 때문이다. 중복순열로 각 cctv가 가질 수 있는 방향의 종류의 가짓수를 구한다. 각 종류별로 구했기 때문에 이를 합쳐야 한다. 그렇기 때문에 중복순열로 이 각 종류별로 해당되는 케이스를 합치면 된다.
이러한 모든 케이스를 구했다면 이 케이스를 분해해서 cctv를 돌려야 한다. 먼저 각 케이스를 가져와서 그 케이스에는 종류별로 부여된 것이 있기 때문에 종류별로 분해한다. 그런다음 방향과 번호를 부여해야 우리는 해당 cctv를 진행시킬 수 있기 때문에 이를 함수로 만들어서 돌려준다.
함수 내에서는 각 번호와 방향 그리고 위치를 가지고 있기 때문에 단순히 주어진 방향으로 진행만 시켜주면 된다. 이를 통해 최종적으로 board에서 남은 0의 수를 구해주면서 최솟값을 구해주면 정답이 갱신된다.
이렇게 Python로 백준의 "감시" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
