| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다.
(중략)
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
풀이
CCTV의 방향을 어떻게 두냐에 따라 사무실 감시 영역이 어떻게 될지는 각 연산을 시도해봐야 알 수 있으므로 모든 경우의 수를 탐색해봐야 하는 브루트포스 문제다. 이 문제에서 겪은 어려움은 배열 상태 관리였다. 탐색을 수행함에 따라 되돌아갈 때는 이전 상태로 배열을 되돌려놓아야 하는데 그걸 수행하지 못하는 코드를 만들었다. 아직도 뭔진 잘 모르겠다.
0. 구현할 것들
재귀 함수로 브루트포스를 할 때 가장 먼저 할 일. 탐색 종료를 위한 플래그를 만들어야 한다. cctv를 대상으로 하기 때문에 매개변수로 넘겨주는 탐색 깊이가 cctv 배열과 크기가 같아질 때를 탐색 종료 기점으로 한다.
매 탐색에서는 1~5번 cctv를 회전시켜주어야 한다. 1, 3, 4번은 4가지 방향을 만들어줄 수 있고 2번은 상하, 좌우로 감시하는 2가지 방향만 있다. 5번은 방향이 없다고 볼 수 있다.
탐색 방향에 따라 감시 영역을 하나씩 둘러볼 수 있는 방향 값 배열을 d=[[0,1],[1,0],[0,-1],[-1,0]]으로 만들었다. x, y 좌표에 이 값들을 더했을 때 벽이 등장하거나 배열 크기를 벗어나는 경우 탐색을 마치고 다음 깊이로 내려간다.
cctv가 있거나 감시한 영역은 그냥 지나친다. 0인 영역은 감시한 영역이므로 다른 값을 저장해준다. (나중에 이 부분을 수정했다.)
1. 배열을 매개변수로 넘기는 재귀호출
사무실 배열을 받고 cctv의 종류와 위치를 cctv 배열에 따로 저장했다. 그리고 모든 cctv에 대한 탐색을 수행하도록 브루트포스 함수를 정의했다. 처음에는 재귀 호출로 들어갈 때마다 배열을 따로 관리할 줄 알았으나 디버깅으로 알게 된 사실은 그렇지 않았다. 다음 깊이로 들어가 다음 cctv의 감시영역을 탐색하면 지금까지 파고든 모든 배열이 함께 변해버린다. 탐색을 마치고 탈출해도 원래 상태의 배열이 남아있지 않는다. 이렇게 되면 애초에 매개변수로 배열을 넘겨준 것이 아니라 매개변수를 타고 변수가 따라와 버린 것이다.
def bruteforce(depth, office_get):
if depth == len(cctv):
global blind_spot
blind_spot = min(blind_count(office_get), blind_spot)
return
cnt_cctv = cctv[depth][0]
cnt_x = cctv[depth][1]
cnt_y = cctv[depth][2]
if cnt_cctv == 1:
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] == 0:
office_get[dx][dy] = 7
dx += d[i][0]
dy += d[i][1]
bruteforce(depth + 1, office_get)
elif cnt_cctv == 2:
elif cnt_cctv == 3:
elif cnt_cctv == 4:
elif cnt_cctv == 5:
얕은 복사가 일어났구나, 싶어서 매개변수로 받은 office_get 배열을 따로 office_new 배열로 깊은 복사를 해주었다. 두 가지 방법을 시도했는데 먼저 같은 크기의 배열로 만들고 저장된 데이터 하나하나 옮겨 담는 방법, 그리고 copy.deepcopy 메서드를 사용해봤다. 결과는 모두 실패. Mutable 객체를 다루는 방법은 따로 정리해봐야겠다.
배열을 관리할 수 있는 다른 방법을 찾아보기로 했다. 이렇게 배열이 따로 관리되지 않는다면 탐색의 과정을 되짚어 복원하는 방법을 직접 구현할 수 밖에.
2. 탐색과정 거꾸로 되돌리기
재귀 탈출에서 탐색과정을 거꾸로 되돌아가지 않는다. 그럼 탈출 전에 내가 탐색한 영역을 원래 상태로 되돌려놓아야 한다. 되돌릴 영역은 이미 탐색한 영역과 똑같으므로 같은 탐색을 수행하며 값 변경을 0에 대한 보수로 해주면 된다. 이전에는 탐색 영역의 값을 7로 바꾸려 했으나 탐색 영역에 10씩 더해주기로 했다. 중복된 영역이라면 10, 20, 30 이런식으로 계속 더해지는 것이다. 그렇게 탐색 중에 사무실 데이터를 확인했을 때 10으로 나눈 나머지가 0이라면 감시 가능한 영역이다. 탈출할 때는 똑같은 탐색을 하며 -10을 더해준다.
def bruteforce(depth, office_get):
if depth == len(cctv):
global blind_spot
blind_spot = min(blind_count(office_get), blind_spot)
return
cnt_cctv = cctv[depth][0]
cnt_x = cctv[depth][1]
cnt_y = cctv[depth][2]
if cnt_cctv == 1:
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i][0]
dy += d[i][1]
bruteforce(depth + 1, office_get)
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i][0]
dy += d[i][1]
elif cnt_cctv == 2:
elif cnt_cctv == 3:
elif cnt_cctv == 4:
elif cnt_cctv == 5:
더 좋은 방법이 있을 것 같지만 머릿속에 떠오른 가장 이해하기 쉬운 방법으로 구현해서 성공했다. 어쨌든 내가 읽기 편한 코드가 나에게 제일 좋은 코드라니까 뭐... 아쉬운 점은 문제에서 N, M 값의 범위를 작게 지정해준 것이라 가능한 방법이란 것이다. 만약 N, M의 범위가 50까지만 간다면 이건 시간초과가 뜰 수도 있을 코드다. 연산 횟수를 두 배로 늘려버렸으니;
정답 코드
※장문 주의※
d = [[0,1],[1,0],[0,-1],[-1,0],[0,1],[1,0]]
N, M = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(N)]
cctv = []
blind_spot = N * M
for i in range(N):
for j in range(M):
if 0 < office[i][j] < 6:
cctv.append([office[i][j], i, j])
def blind_count(office_watch):
count = 0
for i in range(N):
for j in range(M):
if office_watch[i][j] == 0:
count += 1
return count
def bruteforce(depth, office_get):
if depth == len(cctv):
global blind_spot
blind_spot = min(blind_count(office_get), blind_spot)
return
cnt_cctv = cctv[depth][0]
cnt_x = cctv[depth][1]
cnt_y = cctv[depth][2]
if cnt_cctv == 1:
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i][0]
dy += d[i][1]
bruteforce(depth + 1, office_get)
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i][0]
dy += d[i][1]
elif cnt_cctv == 2:
for i in range(2):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i][0]
dy += d[i][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i + 2][0]
dy += d[i + 2][1]
bruteforce(depth + 1, office_get)
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i][0]
dy += d[i][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i + 2][0]
dy += d[i + 2][1]
elif cnt_cctv == 3:
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i][0]
dy += d[i][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i + 1][0]
dy += d[i + 1][1]
bruteforce(depth + 1, office_get)
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i][0]
dy += d[i][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i + 1][0]
dy += d[i + 1][1]
elif cnt_cctv == 4:
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i][0]
dy += d[i][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i + 1][0]
dy += d[i + 1][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i + 2][0]
dy += d[i + 2][1]
bruteforce(depth + 1, office_get)
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i][0]
dy += d[i][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i + 1][0]
dy += d[i + 1][1]
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i + 2][0]
dy += d[i + 2][1]
elif cnt_cctv == 5:
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] += 10
dx += d[i][0]
dy += d[i][1]
bruteforce(depth + 1, office_get)
for i in range(4):
dx = cnt_x
dy = cnt_y
while 0 <= dx < N and 0 <= dy < M:
if office_get[dx][dy] == 6:
break
elif office_get[dx][dy] % 10 == 0:
office_get[dx][dy] -= 10
dx += d[i][0]
dy += d[i][1]
bruteforce(0, office)
print(blind_spot)
