[코딩인터뷰] 백준 14502번

백준 14502번

백준 14502번 연구소 문제는가능한 경우의 수가 많지 않습니다. 그래서 무식하게 벽을 세울 수 있는 모든 경우의 수를 검토해도 시간 안에 풀 수 있습니다. 만약 이게 문제가 아니었다면 바이러스를 기준으로 탐색해서 벽을 더 효율적인 세울 수 있는 방법을 찾아보고 싶네요.

from copy import deepcopy
from collections import deque

def virus():
    global n, m, maps, answer, viruses, dx, dy

    c_maps = deepcopy(maps)

    for v in viruses:
        q = deque()
        q.append(v)
        visited = [[False] * m for _ in range(n)]
        while 0 < len(q):
            c = q.popleft()
            visited[c[0]][c[1]] = True
            # 감염
            c_maps[c[0]][c[1]] = 2

            for i in range(4):
                nx = c[0] + dx[i]
                ny = c[1] + dy[i]
                if 0 <= nx < n and 0<= ny < m and not visited[nx][ny] and (nx,ny) not in q and c_maps[nx][ny] == 0:
                    q.append((nx, ny))

    total = 0
    for ci in range(n):
        for cj in range(m):
            if c_maps[ci][cj] == 0:
                total += 1

    if answer < total:
        answer = total

def dfs(count, x, y):
    global n, m, maps

    if count == 3:
        virus()
        return

    for i in range(x, n):
        t = 0 if x != i else y
        for j in range(t, m):

            if maps[i][j] == 0:
                maps[i][j] = 1
                if j + 1 < m:
                    dfs(count + 1, i, j + 1)
                else:
                    dfs(count + 1, i + 1, 0)
                maps[i][j] = 0

# 0 빈칸 1 벽 2 바이러스
cell = (0, 1, 2)
# 벽 3개만
n, m = map(int, input().split())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

viruses = []
for i in range(n):
    for j in range(m):
        if maps[i][j] == 2:
            viruses.append((i, j))

# L T R B
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

answer = 0
dfs(0, 0, 0)
print(answer)