문제
분석
사물실에 놓인 CCTV(종류, 위치)와 벽의 정보가 주어졌을 때, 가장 사각 지대가 적은 경우를 구하는 문제이다.
사무실에 존재하는 CCTV마다 각 방향을 4가지로 설정할 수 있다. (물론 종류 2와 5는 겹치는 경우가 있지만 구현을 편리하기 위해 각각 4가지 옵션이 있다고 생각한다.)
이때 모든 경우는 4^(CCTV개수)이다.
각 방향을 0, 1, 2, 3이라고 할 때, CCTV개수 만큼 중복을 허용해서 뽑는 중복순열이다.
따라서 python에서 product를 사용하여 모든 경우를 만든다.
이제 위치와 방향이 다 정해졌기 때문에 각 case마다 사각지대를 계산해주면 된다.
def setDirection(type, d)
감시당하는 부분을 표시하기 위해 dxs, dys를 결정해주는 함수이다.
먼저 처음에 dxs, dys = [0,1,0,-1], [1,0,-1,0]로 초기화하고 파라미터로 들어오는 방향 d를 기준으로 종류에 따라 처리한다.
종류 1일 때는 한 방향만 바라보기 때문에 한 방향만 넣은 리스트가 반환된다.
종류 2일 때는 양쪽 방향을 바라보기 때문에 앞서 넣은 방향에 +2를 하여 반대방향도 넣어준다.
종류 3일 때는 직각으로 바라보기 때문에 앞서 넣은 방향에 +1을 하여 넣어준다.
종류 4일 때는 한 방향만 감시하지 않기 때문에 한 방향을 pop해준다.
종류 5일 때는 모든 방향을 바라보고, 돌려도 같은 경우이기 때문에 특별히 처리하지 않는다.
dxs, dys가 결정되면 영역을 넘어가거나 벽(6)을 만날 때까지 모두 감시되는 표시를 해준다.
이때 다른 CCTV가 있는 경우, 그 CCTV를 넘어서도 감시가 되기 때문에 계속 진행하지만 해당 영역에 표시를 하면 CCTV의 종류가 바뀌어 버리므로 표시하는 것은 아무것도 없는 0일 때만 한다.
코드
해결언어 : Python
import sys
input = sys.stdin.readline
from itertools import product
n, m = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(n)]
def in_range(x, y):
return 0<=x<n and 0<=y<m
def getArea(box):
size = 0
for i in range(n):
for j in range(m):
if box[i][j] == 0:
size += 1
return size
def setDirection(type, d):
dxs, dys = [0,1,0,-1], [1,0,-1,0]
if type == 1:
dxs, dys = [dxs[d]], [dys[d]]
elif type == 2:
dxs, dys = [dxs[d], dxs[(d+2)%4]], [dys[d], dys[(d+2)%4]]
elif type == 3:
dxs, dys = [dxs[d], dxs[(d+1)%4]], [dys[d], dys[(d+1)%4]]
elif type == 4:
dxs.pop(d)
dys.pop(d)
return dxs, dys
mn = n*m
pos = []
for i in range(n):
for j in range(m):
if room[i][j] in [1,2,3,4,5]:
pos.append((i, j))
for case in product([0,1,2,3], repeat=len(pos)):
box = [items[:] for items in room]
for (x,y), d in zip(pos, case):
type = room[x][y]
dxs, dys = setDirection(type, d)
for dx, dy in zip(dxs, dys):
nx, ny = x + dx, y + dy
while in_range(nx, ny) and box[nx][ny] != 6:
if box[nx][ny] == 0:
box[nx][ny] = type
nx, ny = nx + dx, ny + dy
mn = min(mn, getArea(box))
print(mn)
2차원 배열을 복사할 때 copy 라이브러리의 deepcopy메소드를 사용하면 코드는 더욱 간결해진다.
그러나 아래와 같이 슬라이싱으로 복사하는 것이 성능은 더 좋았다.
box = [items[:] for items in room]
끝으로..
복잡한 구현 문제는 작은 문제로 나누어 메소드를 잘 정리하는 것이 중요한 것 같다..
