[백준] 15683번 감시
문제 링크
https://www.acmicpc.net/problem/15683
문제 설명
- 감시하는 범위가 각각 다른 5종류의 cctv가 있다
- 감시받지 않는 영역의 최솟값 출력
풀이
- 완전 탐색
- 재귀로 각 cctv가 바라보는 방향의 4가지 경우의 수 모두 구함
- 4 ** len(cctv)
- 2번, 5번은 4가지 방향을 모두 검사하지 않아도 되지만 시간복잡도는 차이 없을 것 같아서 구현의 편의상 그냥 검사했다
- 각 경우의 수마다 감시받지 않는 영역의 넓이를 구함
- 최솟값 출력
코드
def dfs(i):
global min_size
if i == len(cctv):
min_size = min(min_size, get_size())
return
for d in range(4):
dirs[i] = d
dfs(i+1)
def get_size():
new_board = [line[:] for line in board]
for i in range(len(cctv)):
set_board(new_board, i)
return sum([line.count(0) for line in new_board])
def set_board(board, i):
y, x, num = cctv[i]
d = dirs[i]
if num == 1:
set_line(board, y, x, d)
elif num == 2:
set_line(board, y, x, d)
set_line(board, y, x, (d+2)%4)
elif num == 3:
set_line(board, y, x, d)
set_line(board, y, x, (d+1)%4)
elif num == 4:
set_line(board, y, x, d)
set_line(board, y, x, (d+1)%4)
set_line(board, y, x, (d+2)%4)
elif num == 5:
for j in range(4):
set_line(board, y, x, j)
def set_line(board, y, x, d):
while True:
y, x = y + dy[d], x + dx[d]
if 0 <= y < h and 0 <= x < w:
if board[y][x] == 0:
board[y][x] = 7
elif board[y][x] == 6:
break
else:
break
# init
import sys
read = sys.stdin.readline
h, w = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(h)]
cctv = []
for i in range(h):
for j in range(w):
if 1 <= board[i][j] <= 5:
cctv.append([i, j, board[i][j]])
visited = [False] * len(cctv)
dirs = [-1] * len(cctv)
min_size = float('inf')
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1] # 북,동,남,서
# start
dfs(0)
print(min_size)
Author And Source
이 문제에 관하여([백준] 15683번 감시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-15683번-감시
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 완전 탐색
- 재귀로 각 cctv가 바라보는 방향의 4가지 경우의 수 모두 구함
- 4 ** len(cctv)
- 2번, 5번은 4가지 방향을 모두 검사하지 않아도 되지만 시간복잡도는 차이 없을 것 같아서 구현의 편의상 그냥 검사했다
- 각 경우의 수마다 감시받지 않는 영역의 넓이를 구함
- 최솟값 출력
코드
def dfs(i):
global min_size
if i == len(cctv):
min_size = min(min_size, get_size())
return
for d in range(4):
dirs[i] = d
dfs(i+1)
def get_size():
new_board = [line[:] for line in board]
for i in range(len(cctv)):
set_board(new_board, i)
return sum([line.count(0) for line in new_board])
def set_board(board, i):
y, x, num = cctv[i]
d = dirs[i]
if num == 1:
set_line(board, y, x, d)
elif num == 2:
set_line(board, y, x, d)
set_line(board, y, x, (d+2)%4)
elif num == 3:
set_line(board, y, x, d)
set_line(board, y, x, (d+1)%4)
elif num == 4:
set_line(board, y, x, d)
set_line(board, y, x, (d+1)%4)
set_line(board, y, x, (d+2)%4)
elif num == 5:
for j in range(4):
set_line(board, y, x, j)
def set_line(board, y, x, d):
while True:
y, x = y + dy[d], x + dx[d]
if 0 <= y < h and 0 <= x < w:
if board[y][x] == 0:
board[y][x] = 7
elif board[y][x] == 6:
break
else:
break
# init
import sys
read = sys.stdin.readline
h, w = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(h)]
cctv = []
for i in range(h):
for j in range(w):
if 1 <= board[i][j] <= 5:
cctv.append([i, j, board[i][j]])
visited = [False] * len(cctv)
dirs = [-1] * len(cctv)
min_size = float('inf')
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1] # 북,동,남,서
# start
dfs(0)
print(min_size)
Author And Source
이 문제에 관하여([백준] 15683번 감시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-15683번-감시
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def dfs(i):
global min_size
if i == len(cctv):
min_size = min(min_size, get_size())
return
for d in range(4):
dirs[i] = d
dfs(i+1)
def get_size():
new_board = [line[:] for line in board]
for i in range(len(cctv)):
set_board(new_board, i)
return sum([line.count(0) for line in new_board])
def set_board(board, i):
y, x, num = cctv[i]
d = dirs[i]
if num == 1:
set_line(board, y, x, d)
elif num == 2:
set_line(board, y, x, d)
set_line(board, y, x, (d+2)%4)
elif num == 3:
set_line(board, y, x, d)
set_line(board, y, x, (d+1)%4)
elif num == 4:
set_line(board, y, x, d)
set_line(board, y, x, (d+1)%4)
set_line(board, y, x, (d+2)%4)
elif num == 5:
for j in range(4):
set_line(board, y, x, j)
def set_line(board, y, x, d):
while True:
y, x = y + dy[d], x + dx[d]
if 0 <= y < h and 0 <= x < w:
if board[y][x] == 0:
board[y][x] = 7
elif board[y][x] == 6:
break
else:
break
# init
import sys
read = sys.stdin.readline
h, w = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(h)]
cctv = []
for i in range(h):
for j in range(w):
if 1 <= board[i][j] <= 5:
cctv.append([i, j, board[i][j]])
visited = [False] * len(cctv)
dirs = [-1] * len(cctv)
min_size = float('inf')
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1] # 북,동,남,서
# start
dfs(0)
print(min_size)
Author And Source
이 문제에 관하여([백준] 15683번 감시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-15683번-감시저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)