[백준] 14502. 연구소 - Python

[Gold IV]

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

14502번: 연구소

풀이

1. 백트래킹을 통해 미로에서 벽을 놓을 위치 세 곳을 선택한다. -> 나중에는 순열로 해결해도 가능
2. (1)을 통해 3개의 벽을 세웠으면, 해당 연구실 지도를 deepcopy(깊은 복사를 해야 원본이 변경되지 않음)를 통해

테스트 지도를 복사하고, 상, 하, 좌, 우를 번갈아가며 BFS로 지도를 탐색한다.

(처음에는 방문했던 노드를 재방문 하는 것을 피하려고 visited 배열을 사용했지만, 정확한 시간복잡도와 이유를 모르나 각 벽이 세워지는

경우에 따라 visited배열을 초기화하고 사용해야되기 때문에 시간복잡도가 증가하는 것 같았다. 또한, Python 3를 사용해서는 해결되지

않아 PyPy3를 사용하여 문제를 해결하였다.)

나중에 알게된 사실은, 조합(combination)을 사용하면 시간복잡도가 현저히 줄어들어 Python 3로도 해결 가능한 것을 알게되었다.

(추후 조합을 사용해서도 구현해볼 예정)

from collections import deque
import copy
import sys

global laboratoryMap
# global visited
global n
global m
global dx
global dy
global ans
ans = 0
# visited = []
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# def varClear():
#     global visited, n, m
#     visited = [[False for j in range (m)] for i in range(n)]

def bfs():
    global visited, n, m, ans
    cnt = 0
    queue = deque()
    testMap = copy.deepcopy(laboratoryMap)

    for i in range(n):
        for j in range(m):
            if testMap[i][j] == 2:
                queue.append([i, j])
                # visited[i][j] = True

    while queue:
        cur = queue.popleft()
        # visited[cur[0]][cur[1]] = True

        for i in range(4):
            next = [cur[0] + dy[i],cur[1] + dx[i]]

            if (0 <= next[0] < n) and (0 <= next[1] < m):
                # if not visited[next[0]][next[1]]:
                if testMap[next[0]][next[1]] == 0:
                    testMap[next[0]][next[1]] = 2
                    queue.append([next[0], next[1]])
                    # visited[next[0]][next[1]] = True

    cnt = sum(row.count(0) for row in testMap)
    ans = max(cnt, ans)

def makeWall(cnt):
    global n, m, laboratoryMap

    if cnt == 3:
        bfs()
        # varClear()
        return

    for i in range(n):
        for j in range(m):
            if laboratoryMap[i][j] == 0:
                laboratoryMap[i][j] = 1
                makeWall(cnt + 1)
                laboratoryMap[i][j] = 0


# main
n ,m = map(int, sys.stdin.readline().split())
laboratoryMap = []
virus = []
visited = [[False for j in range(m)] for i in range(n)]

for i in range(n):
    laboratoryMap.append(list(map(int, sys.stdin.readline().split())))

makeWall(0)

print(ans)