[백준/파이썬] 15683번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 15683번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.
1번 2번 3번 4번 5번
1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0
지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. …
입력 요약
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력 요약
첫째 줄에 사각 지대의 최소 크기를 출력한다.
코드
n, m = map(int, input().split())
cells = [list(map(int, input().split())) for _ in range(n)]
infos = [[] for _ in range(7)]
for i in range(n):
for j in range(m):
infos[cells[i][j]].append((i, j))
##for row in infos: print(row)
cases = {}
def backTracking(camType, case):
if len(case) >= len(infos[camType]):
cases[camType].append(case)
return
if camType == 5: backTracking(camType, case+[0])
elif camType == 2:
backTracking(camType, case+[0])
backTracking(camType, case+[1])
else:
for i in range(4): backTracking(camType, case+[i])
for i in range(1,6):
if len(infos[i]) > 0:
cases[i] = []
backTracking(i, [])
##for key, value in cases.items(): print(key, value)
combs = []
def getCombs(depth, comb):
if depth == 5:
combs.append(comb)
return
try:
for i in range(len(cases[depth+1])): getCombs(depth+1, comb+[i])
except KeyError: getCombs(depth+1, comb+[-1])
getCombs(0, [-1])
def setToWatched(cells, direction, diff):
if not(0 <= r+direction[0]*diff < n) or\
not(0 <= c+direction[1]*diff < m) or\
cells[r+direction[0]*diff][c+direction[1]*diff] == 6: return
if cells[r+direction[0]*diff][c+direction[1]*diff] == 0:
cells[r+direction[0]*diff][c+direction[1]*diff] = '#'
setToWatched(cells, direction, diff+1)
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
minBlinds = 64
for comb in combs:
tmpCells = [cells[i].copy() for i in range(n)]
## for row in tmpCells: print(row)
for i in range(1,6):
for j in range(len(infos[i])):
r, c = infos[i][j][0], infos[i][j][1]
if i == 5:
for direction in directions: setToWatched(tmpCells, direction, 1)
elif i == 2:
setToWatched(tmpCells, directions[cases[i][comb[i]][j]], 1)
setToWatched(tmpCells, directions[cases[i][comb[i]][j]+2], 1)
else:
setToWatched(tmpCells, directions[cases[i][comb[i]][j]], 1)
if i > 1: setToWatched(tmpCells, directions[(cases[i][comb[i]][j]+1)%4], 1)
if i > 3: setToWatched(tmpCells, directions[(cases[i][comb[i]][j]+2)%4], 1)
blinds = 0
for row in tmpCells: blinds += row.count(0)
minBlinds = min(minBlinds, blinds)
## print('=====================')
## print(comb)
## for row in tmpCells: print(*row)
## print('=====================')
print(minBlinds)
설명
핵심은 구현 관점에서 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기