[Python]14502. 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

---

 

문제를 풀기전에 제약조건을 먼저 확인하고 경우의수를 계산해본다.

3 ≤ N, M ≤ 8 이고 벽은 3개를 배치하므로,

N*M Combination 3 * N * M = 64C3 * 8 * 8 = 약 2백만 --> 완전탐색 가능하므로 완탐 실시한다.

 

알고리즘

 

from copy import deepcopy

def bfs(MAP):
​​​​global n, m
​​​​queue = []
​​​​dist = [[0] * m for _ in range(n)]

​​​​for r in range(n): #바이러스와 벽의 위치를 찾음
​​​​​​​​for c in range(m):
​​​​​​​​​​​​if MAP[r][c] == 2:
​​​​​​​​​​​​​​​​queue.append((r,c)) # 바이러스는 큐에 넣음
​​​​​​​​​​​​if MAP[r][c] == 1:
​​​​​​​​​​​​​​​​dist[r][c] = -1 # 벽은 -1로 변경

​​​​while queue:
​​​​​​​​curr_y, curr_x = queue.pop(0)
​​​​​​​​for i in range(4):
​​​​​​​​​​​​next_y = curr_y + direction[i][0]
​​​​​​​​​​​​next_x = curr_x + direction[i][1]
​​​​​​​​​​​​if 0 <= next_y < n and 0 <= next_x < m:
​​​​​​​​​​​​​​​​if MAP[next_y][next_x] == 0 and dist[next_y][next_x] == 0:
​​​​​​​​​​​​​​​​​​​​MAP[next_y][next_x] = 2
​​​​​​​​​​​​​​​​​​​​dist[next_y][next_x] = dist[curr_y][curr_x] + 1
​​​​​​​​​​​​​​​​​​​​queue.append((next_y, next_x))

def getSafeZone(MAP):
​​​​cnt = 0
​​​​for r in range(n):
​​​​​​​​for c in range(m):
​​​​​​​​​​​​if MAP[r][c] == 0:
​​​​​​​​​​​​​​​​cnt += 1
​​​​return cnt

def dfs(depth):
​​​​global answer, n, m
​​​​if depth == 3:
​​​​​​​​MAP2 = deepcopy(MAP)
​​​​​​​​bfs(MAP2)
​​​​​​​​sz = getSafeZone(MAP2)
​​​​​​​​answer = max(answer, sz)
​​​​​​​​return
​​​​
​​​​for r in range(n):
​​​​​​​​for c in range(m):
​​​​​​​​​​​​if not check[r][c] and MAP[r][c] == 0:
​​​​​​​​​​​​​​​​check[r][c] = True
​​​​​​​​​​​​​​​​MAP[r][c] = 1
​​​​​​​​​​​​​​​​dfs(depth+1)
​​​​​​​​​​​​​​​​check[r][c] = False
​​​​​​​​​​​​​​​​MAP[r][c] = 0

n, m = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(n)]
check = [[False]*m for _ in range(n)]
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
answer = 0
dfs(0)
print(answer)