문제
감시 [백준 15683]
https://www.acmicpc.net/problem/15683
풀이
처음 풀이
처음에는 길게 코딩했고 코드가 길어지다 보니 에러타이핑도 많은 부분에서 발생하여 시간이 많이 걸리고, 채점시간, 메모리 면에서도 좋지 않은 코드를 작성하였다.
- cctv 가 있는 위치와 번호를 리스트에 정리
- 깊이를 더해가며 dfs 함수에서 서로 다른 방향마다 비춰지는 사무실을 전달
- watch 함수를 만들어 cctv 번호마다 비출 수 있는 사무실 공간을 비추고 사무실을 다시 return
두번째 풀이
첫번째로 하니 watch 함수가 굉장히 길어졌다.
- cctv 번호마다 비춰야하는 방향을 저장한 dict을 선언
- board 를 검사하며 cctv 이면 해당 cctv가 볼수 있는 좌표를 집합에 저장하여 cctv 리스트에 추가
- set의 길이가 적은 조합을 찾으며 dfs 진행
코드
1
import copy
n , m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
# 입력
cctv = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for i in range(n):
for j in range(m):
if board[i][j] != 0 and board[i][j] != 6:
cctv.append((board[i][j], i, j))
# cctv 에 cctv 번호와 좌표 추가
k = len(cctv)
result = n * m
def watch(n_cctv, board, d):
new_board = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if board[i][j] != 0:
new_board[i][j] = board[i][j]
ct, x, y = n_cctv
# cctv 번호가 1일때
if ct == 1:
while True:
#한방향만 탐색
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
# cctv 번호가 2일때
elif ct == 2:
while True:
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
ct, x, y = n_cctv
# x, y 초기화 후 반대 방향 탐색
while True:
nx = x - dx[d]
ny = y - dy[d]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
# cctv 번호가 3일때
elif ct == 3:
while True:
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
ct, x, y = n_cctv
d = (d + 1) % 4
# 방향 오른쪽으로 돌리고 탐색
while True:
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
# cctv 번호가 4일때
elif ct == 4:
temp = [num for num in range(4) if num != d]
# d가 없는 방향만 탐색 즉 3방향 탐색
for i in temp:
ct, x, y = n_cctv
while True:
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
# cctv 번호가 5일때
else:
#모두 보기
for i in range(4):
ct, x, y = n_cctv
while True:
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if new_board[nx][ny] == 6:
break
if new_board[nx][ny] == 0:
new_board[nx][ny] = '#'
x, y = nx, ny
else:
break
return new_board
def dfs(num, board):
global result
if num >= k:
count = 0
for i in range(n):
for j in range(m):
if board[i][j] == 0:
count += 1
result = min(result, count)
return
n_cctv = cctv[num]
if n_cctv[0] == 1 or n_cctv[0] == 4 or n_cctv[0] == 3:
for d in range(4):
new_board = watch(n_cctv, board, d)
dfs(num + 1, new_board)
elif n_cctv[0] == 2:
for d in [0, 1]:
new_board = watch(n_cctv, board, d)
dfs(num + 1, new_board)
else:
new_board = watch(n_cctv, board, 0)
dfs(num + 1, new_board)
return
dfs(0, board)
print(result)2
# 벽은 감시할 수 없고, 통과도 못 한다. CCTV는 회전시킬 수 있다. 5가지 타입의 CCTV가 있다. CCTV가 못 비추는 사각지대가 최소가 되게 하는 사각지대갯수를 구해라.
blind = 0
cctv = []
dx = [0,0,-1,1] # 오,왼,위,아래
dy = [1,-1,0,0]
# cctv로 비출 수 있는 구역들 다 비추기
def watch(x,y,check_list):
s=set() # visited 대신 set 사용. 갔던 데 또 가도 되는 대신 합쳐지기때문
for d in check_list: # d=0 check_list = [0,1]
nx = x
ny = y
while True:
nx += dx[d]
ny += dy[d] # visited 했어도 또 비춰도 되므로 set 사용. 중복
if nx<0 or ny<0 or nx>=N or ny>=M or graph[nx][ny]==6:
break
elif graph[nx][ny]==0:
s.add((nx,ny))
return s
type = {
1:[[0],[1],[2],[3]],
2:[[0,1],[2,3]],
3:[[0,2],[0,3],[1,2],[1,3]],
4:[[0,1,2],[0,1,3],[2,3,0],[2,3,1]],
5:[[0,1,2,3]]
}
N,M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)]
# cctv별로 비출 수 있는 경우의 수 set조합들 만들어 cctv에 저장.
for i in range(N):
for j in range(M):
if graph[i][j]==0:
blind+=1 # 안보이는 지역 수
elif graph[i][j]!=0 and graph[i][j]!=6:
cctv.append([watch(i,j,check_list) for check_list in type[graph[i][j]]]) # check_list = [0,1] 한 경우마다 비춰지는 좌표들 set
# 가장 넓은 범위로 비추는 watched_set 만들기
watched_set = [set()]
def dfs(depth,prev_set):
if depth==len(cctv):
if len(prev_set)>len(watched_set[0]): # 더 많이 비추면 갱신
watched_set[0] = prev_set
return
for cur_set in cctv[depth]: # 조합1, 조합2..
dfs(depth+1,prev_set|cur_set) # prev_set | 조합1
dfs(0,set())
print(blind - len(watched_set[0]))
.