출처 : https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할
www.acmicpc.net
아래 코드는 맨 처음에 썼던 알고리즘인데
(순위권 코드를 이해하고나서 처음부터 안보고 쭉 코딩한것도 있는데 그 코드는 맨 아래에 있다.)
정말 정말 그저 의식의 흐름에 따라 코드화 한 것이라 엄청 길고 시간, 메모리도 많이 잡아먹는다.
(알고리즘 문제 풀면서 이렇게 길게 써본건 처음!!;;)
모든 경우의 수를 따져봐야 하는 브루트포스 문제인지라,
dfs 재귀 함수를 이용해서 해결하려 했는데
문제는, 매번 재귀 함수를 호출할때마다 배열을 매번 복사해서 새롭게 할당받을 경우
채점 시간이나 메모리 측면에서 통과하기 힘들 것 같았다.
재귀 함수 호출할 때마다 배열을 복사해서 새로 할당받게 하지 않고,
하나의 배열을 서로 공유하게 해서
배열 안에 담긴 값을 계속해서 수정하는 식으로 하면, 위에서 생각했던 것 보다는 나을 것 같았다.
잉? 근데 지금 생각해보니 신기한게
sys.setrecursionlimit을 안해줬는데도 통과가 됐네..?
채점에 사용된 문제들이 (파이썬에서 기본으로 설정되어있는)최대깊이를 넘어서지 않나보다.
< 문제 풀이 생각 >
감시가 되고 있는 장소를 단순히 '#'라고만 표시하지 않고, 몇개의 CCTV에 의해 감시되고 있는지 추가 정보를 넣는게 어떨까?
['#', 1] : 카메라 1대에 의해 감시되고 있는 공간
['#', 2] : 카메라 2대에 의해 감시되고 있는 공간
...
['#', n] : 카메라 n대에 의해 감시되고 있는 공간
from collections import deque
## 빈 공간의 수를 구한다.
def empty(map_array):
cnt = 0
for i in range(len(map_array)):
for j in range(len(map_array[0])):
if map_array[i][j] == 0:
cnt = cnt+1
return cnt
## [x,y]위치로부터 윗방향을 #으로 만들어준다.
def up(map_array, x, y): ## 맵, CCTV의 x,y좌표
for i in range(x-1, -1, -1):
## 벽을 만났다
if map_array[i][y] == 6:
break
## CCTV를 만났다.
elif map_array[i][y]==1 or map_array[i][y]==2 or map_array[i][y]==3 or map_array[i][y]==4 or map_array[i][y]==5:
continue
## 빈 공간을 만났다.
elif map_array[i][y]==0:
map_array[i][y] = ['#',1]
## 다른 CCTV가 감시하고 있는 공간을 만났다.
else:
map_array[i][y][1] = map_array[i][y][1] + 1
## up을 회수한다.
def reverse_up(map_array, x, y): ## 맵, CCTV의 x,y좌표
for i in range(x-1, -1, -1):
## 벽을 만났다
if map_array[i][y] == 6:
break
## CCTV를 만났다.
elif map_array[i][y]==1 or map_array[i][y]==2 or map_array[i][y]==3 or map_array[i][y]==4 or map_array[i][y]==5:
continue
## '#'를 만난다.
else:
## '#'가 1개의 CCTV에 의해 감시되고 있었다면?
if map_array[i][y][1] == 1:
map_array[i][y] = 0 ## 빈공간으로 만들어준다.
## '#'가 2개 이상의 CCTV에 의해 감시되고 있었다면?
else:
map_array[i][y][1] = map_array[i][y][1] - 1
## [x,y]위치로부터 아랫방향을 #으로 만들어준다.
def down(map_array, x, y):
for i in range(x+1, len(map_array)):
## 벽을 만났다.
if map_array[i][y] == 6:
break
## CCTV를 만났다.
elif map_array[i][y]==1 or map_array[i][y]==2 or map_array[i][y]==3 or map_array[i][y]==4 or map_array[i][y]==5:
continue
## 빈 공간을 만났다.
elif map_array[i][y]==0:
map_array[i][y] = ['#',1]
## 다른 CCTV가 감시하고 있는 공간을 만났다.
else:
map_array[i][y][1] = map_array[i][y][1] + 1
## down한것을 회수한다.
def reverse_down(map_array, x, y):
for i in range(x+1, len(map_array)):
## 벽을 만났다.
if map_array[i][y] == 6:
break
## CCTV를 만났다.
elif map_array[i][y]==1 or map_array[i][y]==2 or map_array[i][y]==3 or map_array[i][y]==4 or map_array[i][y]==5:
continue
## '#'를 만난다.
else:
## '#'가 1개의 CCTV에 의해 감시되고 있었다면?
if map_array[i][y][1] == 1:
map_array[i][y] = 0 ## 빈공간으로 만들어준다.
## '#'가 2개 이상의 CCTV에 의해 감시되고 있었다면?
else:
map_array[i][y][1] = map_array[i][y][1] - 1
## [x,y]위치로부터 오른쪽방향을 #으로 만들어준다.
def right(map_array, x, y):
for i in range(y+1, len(map_array[0])):
## 벽을 만났다.
if map_array[x][i] == 6:
break
## CCTV를 만났다.
elif map_array[x][i]==1 or map_array[x][i]==2 or map_array[x][i]==3 or map_array[x][i]==4 or map_array[x][i]==5:
continue
## 빈 공간을 만났다.
elif map_array[x][i]==0:
map_array[x][i] = ['#',1]
## 다른 CCTV가 감시하고 있는 공간을 만났다.
else:
map_array[x][i][1] = map_array[x][i][1] + 1
## right을 회수한다.
def reverse_right(map_array, x, y):
for i in range(y+1, len(map_array[0])):
## 벽을 만났다.
if map_array[x][i] == 6:
break
## CCTV를 만났다.
elif map_array[x][i]==1 or map_array[x][i]==2 or map_array[x][i]==3 or map_array[x][i]==4 or map_array[x][i]==5:
continue
## '#'를 만난다.
else:
## '#'가 1개의 CCTV에 의해 감시되고 있었다면?
if map_array[x][i][1] == 1:
map_array[x][i] = 0 ## 빈공간으로 만들어준다.
## '#'가 2개 이상의 CCTV에 의해 감시되고 있었다면?
else:
map_array[x][i][1] = map_array[x][i][1] - 1
## [x,y]위치로부터 왼쪽방향을 #으로 만들어준다.
def left(map_array, x, y):
for i in range(y-1, -1, -1):
## 벽을 만났다.
if map_array[x][i] == 6:
break
## CCTV를 만났다.
elif map_array[x][i]==1 or map_array[x][i]==2 or map_array[x][i]==3 or map_array[x][i]==4 or map_array[x][i]==5:
continue
## 빈 공간을 만났다.
elif map_array[x][i]==0:
map_array[x][i] = ['#',1]
## 다른 CCTV가 감시하고 있는 공간을 만났다.
else:
map_array[x][i][1] = map_array[x][i][1] + 1
## left를 회수한다.
def reverse_left(map_array, x, y):
for i in range(y-1, -1, -1):
## 벽을 만났다.
if map_array[x][i] == 6:
break
## CCTV를 만났다.
elif map_array[x][i]==1 or map_array[x][i]==2 or map_array[x][i]==3 or map_array[x][i]==4 or map_array[x][i]==5:
continue
## '#'를 만난다.
else:
## '#'가 1개의 CCTV에 의해 감시되고 있었다면?
if map_array[x][i][1] == 1:
map_array[x][i] = 0 ## 빈공간으로 만들어준다.
## '#'가 2개 이상의 CCTV에 의해 감시되고 있었다면?
else:
map_array[x][i][1] = map_array[x][i][1] - 1
def dfs(map_array, location):
global minv
if not location:
empty_cnt = empty(map_array)
if empty_cnt < minv:
minv = empty_cnt
else:
## CCTV위치
a,b = location[0][0], location[0][1]
## 1번 CCTV
if map_array[a][b] == 1:
for dv in direction[1]:
## 감시 공간 '#'을 업데이트 하고
if dv[0] == 1:
up(map_array, a, b)
if dv[1] == 1:
right(map_array, a, b)
if dv[2] == 1:
down(map_array, a, b)
if dv[3] == 1:
left(map_array, a, b)
## dfs 재귀 함수
dfs(map_array, location[1:])
## 90도 회전해서 새로 감시하기 위해 이전에 감시 하던 공간을 회수한다.
if dv[0] == 1:
reverse_up(map_array, a, b)
if dv[1] == 1:
reverse_right(map_array, a, b)
if dv[2] == 1:
reverse_down(map_array, a, b)
if dv[3] == 1:
reverse_left(map_array, a, b)
## 2번 CCTV
if map_array[a][b] == 2:
for dv in direction[2]:
## 감시 공간 '#'을 업데이트 하고
if dv[0] == 1:
up(map_array, a, b)
if dv[1] == 1:
right(map_array, a, b)
if dv[2] == 1:
down(map_array, a, b)
if dv[3] == 1:
left(map_array, a, b)
## dfs 재귀 함수
dfs(map_array, location[1:])
## 90도 회전해서 새로 감시하기 위해 이전에 감시 하던 공간을 회수한다.
if dv[0] == 1:
reverse_up(map_array, a, b)
if dv[1] == 1:
reverse_right(map_array, a, b)
if dv[2] == 1:
reverse_down(map_array, a, b)
if dv[3] == 1:
reverse_left(map_array, a, b)
## 3번 CCTV
if map_array[a][b] == 3:
for dv in direction[3]:
## 감시 공간 '#'을 업데이트 하고
if dv[0] == 1:
up(map_array, a, b)
if dv[1] == 1:
right(map_array, a, b)
if dv[2] == 1:
down(map_array, a, b)
if dv[3] == 1:
left(map_array, a, b)
## dfs 재귀 함수
dfs(map_array, location[1:])
## 90도 회전해서 새로 감시하기 위해 이전에 감시 하던 공간을 회수한다.
if dv[0] == 1:
reverse_up(map_array, a, b)
if dv[1] == 1:
reverse_right(map_array, a, b)
if dv[2] == 1:
reverse_down(map_array, a, b)
if dv[3] == 1:
reverse_left(map_array, a, b)
## 4번 CCTV
if map_array[a][b] == 4:
for dv in direction[4]:
## 감시 공간 '#'을 업데이트 하고
if dv[0] == 1:
up(map_array, a, b)
if dv[1] == 1:
right(map_array, a, b)
if dv[2] == 1:
down(map_array, a, b)
if dv[3] == 1:
left(map_array, a, b)
## dfs 재귀 함수
dfs(map_array, location[1:])
## 90도 회전해서 새로 감시하기 위해 이전에 감시 하던 공간을 회수한다.
if dv[0] == 1:
reverse_up(map_array, a, b)
if dv[1] == 1:
reverse_right(map_array, a, b)
if dv[2] == 1:
reverse_down(map_array, a, b)
if dv[3] == 1:
reverse_left(map_array, a, b)
## 5번 CCTV
if map_array[a][b] == 5:
## direction[5]에는 값이 하나밖에 없다.
## direction[5] = [[1,1,1,1]]
for dv in direction[5]:
## 감시 공간 '#'을 업데이트 하고
if dv[0] == 1:
up(map_array, a, b)
if dv[1] == 1:
right(map_array, a, b)
if dv[2] == 1:
down(map_array, a, b)
if dv[3] == 1:
left(map_array, a, b)
## dfs 재귀 함수
dfs(map_array, location[1:])
## 새로운 방향에 대해서 해줄 필요가 없으므로 회수할 필요가 없다.
## 1~5 : CCTV
## 0 : 빈 공간
## 6 : 벽
## CCTV는 빈 공간 혹은 CCTV는 통과할수 있지만, 벽은 통과하지 못한다.
if __name__ == '__main__':
N,M = map(int, input().split())
map_array = [list(map(int, input().split())) for _ in range(N)]
## CCTV위치를 담는 큐(=location)를 만들자. 몇번 CCTV인지는 중요하지 않다.
location = deque()
for i in range(N):
for j in range(M):
## 벽도 아니고 빈 공간도 아닐때 append 한다.
## 초기값이기 때문에 map_array에 '#'는 존재하지 않는다.
if map_array[i][j]!=6 and map_array[i][j]!=0:
location.append([i, j])
location = list(location)
## 1번~5번 CCTV의 감시 가능한 영역에 대한 정보
## [up,right,down,left]의 리스트 값을 갖도록 할 것이다.
## 각 원소 값이 0이면 고려하지 않고 1이면 고려하도록 한다.
direction = dict()
##초기화
direction[1] = deque()
direction[2] = deque()
direction[3] = deque()
direction[4] = deque()
direction[5] = deque()
## 1번 CCTV의 가능한 방향은 4개
direction[1].append([1,0,0,0])
direction[1].append([0,1,0,0])
direction[1].append([0,0,1,0])
direction[1].append([0,0,0,1])
## 2번 CCTV의 가능한 방향은 2개
direction[2].append([1,0,1,0])
direction[2].append([0,1,0,1])
## 3번 CCTV의 가능한 방향은 4개
direction[3].append([1,1,0,0])
direction[3].append([0,1,1,0])
direction[3].append([0,0,1,1])
direction[3].append([1,0,0,1])
## 4번 CCTV의 가능한 방향은 4개
direction[4].append([1,1,0,1])
direction[4].append([1,1,1,0])
direction[4].append([0,1,1,1])
direction[4].append([1,0,1,1])
## 5번 CCTV의 가능한 방향은 1개
direction[5].append([1,1,1,1])
## CCTV를 배치하고 나서 빈 공간에 대한 수(최솟값 minv를 계속 업데이트해줘야 한다.)
minv = N*M
dfs(map_array, location)
print(minv)
제출 결과 통과는 되었지만.. 순위권에 있는 사람들과의 격차가 엄청나다
도대체 어떻게 구현했길래.. 이 문제를 푸는데 저 짧은 코드 길이에, 짧은 시간이라니 ..
웬만하면 만족하고 넘어가는데 이건 너무 격차가 커서 참고를 해야한다. (무조건..)
순위권 코드 이해하고 나서 처음부터 다시 작성해본 코드
In [28]:
## x,y : cctv 위치
## direction : 감시 방향 (0:up, 1:right, 2:down, 3:left)
def watch(x, y, direction):
return_set = set()
for d in direction:
new_x = x
new_y = y
while(1):
new_x = new_x+dx[d]
new_y = new_y+dy[d]
if not(0<=new_x<N and 0<=new_y<M): break
if office_array[new_x][new_y]==6: break
## set.add(리스트) : 불가능, 에러 발생
## set.add(튜플) : 가능
if office_array[new_x][new_y]==0: return_set.add((new_x,new_y))
return return_set
In [29]:
def dfs(n, union_set):
global maxv
if n==len(cctv_allcase):
if maxv < len(union_set):
maxv = len(union_set)
return
for i in cctv_allcase[n]:
dfs(n+1, union_set|i)
In [30]:
if __name__ == '__main__':
## cctv_allcase 리스트의 길이 = cctv 총 개수
## eg. cctv_allcase의 각 원소 = 각 cctv의 모든 가능한 감시영역에 대한 좌표정보
## 예를들어 cctv_allcase[0]에 1번 cctv에 대한 정보가 있다고 한다면
## cctv_allcase[0]안에는 4개의 원소가 있을 것이다. 4방향에 대해 감시가 가능하므로.
## 감시할 수 있는 방향에 대해서 감시 가능한 영역들을 좌표들로 저장해놓은 것.
cctv_allcase = []
## up, right, down, left 순서
Up, Right, Down, Left = 0, 1, 2, 3
dx = (-1,0,1,0)
dy = (0,1,0,-1)
## 세로N 가로M 크기
N,M = map(int, input().split())
## 사무실 맵 정보
office_array = [list(map(int, input().split())) for _ in range(N)]
## cctv_allcase, empty 업데이트 (empty는 0으로 이루어진 공간을 의미한다.)
empty = 0
for i in range(N):
for j in range(M):
if office_array[i][j] == 0: empty = empty + 1
elif office_array[i][j] == 1: ## 1번 cctv
cctv_allcase.append([watch(i,j,[Up]), watch(i,j,[Right]), watch(i,j,[Down]), watch(i,j,[Left])])
elif office_array[i][j] == 2: ## 2번 cctv
cctv_allcase.append([watch(i,j,[Up,Down]), watch(i,j,[Right,Left])])
elif office_array[i][j] == 3: ## 3번 cctv
cctv_allcase.append([watch(i,j,[Up,Right]), watch(i,j,[Right,Down]), watch(i,j,[Down,Left]), watch(i,j,[Left,Up])])
elif office_array[i][j] == 4: ## 4번 cctv
cctv_allcase.append([watch(i,j,[Up,Right,Down]), watch(i,j,[Right,Down,Left]), watch(i,j,[Down,Left,Up]), watch(i,j,[Left,Up,Right])])
elif office_array[i][j] == 5: ## 5번 cctv
cctv_allcase.append([watch(i,j,[Up,Right,Down,Left])])
## maxv : 사무실에 존재하는 모든 cctv에 대해서, 감시 가능한 영역의 최대크키
maxv = 0
dfs(0,set())
## 빈 공간의 최소값
print(empty - maxv)
'알고리즘 > [Python] 백준' 카테고리의 다른 글
| (Python) 백준 6087번 : 레이저 통신 (0) | 2020.02.16 |
|---|---|
| (Python) 백준 1547번 : 공 (0) | 2020.02.13 |
| (Python) 백준 14889번 : 스타트와 링크 (0) | 2020.02.12 |
| (Python) 백준 14891번 : 톱니바퀴 (0) | 2020.02.06 |
| (Python) 백준 5397번 : 키로거 (0) | 2020.02.06 |