[백준] 14502 연구소 python

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

14502번: 연구소

백트래킹과 그래프 탐색 알고리즘을 모두 사용해야하는 문제이다

3개의 벽을 설치할 땐 백트래킹을 설치한 이후 바이러스가 전파되는 것은 그래프 탐색(BFS를 사용했다)을 하면된다.

바이러스 전파가 끝나면 이차원 배열에서 안전한 구역을 찾으면 된다.

# import sys; input = sys.stdin.readline
from collections import deque


def bfs():
    global N, M, _map, viruses
    ret = 0
    visit = [[0 for _ in range(M)] for _ in range(N)]
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # 1 breadth first search
    q = deque()
    for virus in viruses:
        q.append(virus)

    while q:
        vr, vc = q.popleft()
        if visit[vr][vc]:
            continue
        visit[vr][vc] = 1
        for dd in d:
            nvr = vr + dd[0]
            nvc = vc + dd[1]
            if 0 > nvr or nvr >= N or 0 > nvc or nvc >= M:
                continue
            if visit[nvr][nvc]:
                continue
            if _map[nvr][nvc] == 1:
                continue
            q.append((nvr, nvc))


    # 3 After BFS, calculate safe area
    for r in range(N):
        for c in range(M):
            if not visit[r][c] and not _map[r][c]:
                ret += 1

    return ret


def backtrack(ind, count):
    global N, M, _map, answer
    if count == 3:
        # 2 BFS for spreading virus
        tmp = bfs()
        answer = max(answer, tmp)
        return
    if ind == N * M:
        return
    # 1  backtracking for selecting wall position
    # ind = r * M + c
    r = ind // M
    c = ind % M
    if not _map[r][c]:
        _map[r][c] = 1
        backtrack(ind+1, count+1)
        _map[r][c] = 0
    backtrack(ind+1, count)


def main():
    # 0 input
    global N, M, _map, viruses, answer
    N, M = map(int, input().split())
    _map = []
    viruses = []
    for i in range(N):
        _map.append(list(map(int, input().split())))
        for j in range(M):
            if _map[i][j] == 2:
                viruses.append((i, j))

    # 1 calculate max area
    answer = 0
    backtrack(0, 0)

    # 2 output
    print(answer)

if __name__ == "__main__":
    main()