[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)