백준 - 14502(연구소, 파이썬)

 

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

14502번: 연구소

문제 이해

• N * M 크기의 연구소에 바이러스가 퍼진다. 이때 벽을 3개 세워 안전구역을 최대한 많이 확보할 때 안전구역의 최대값을 구하는 문제
• 2는 바이러스, 1은 벽, 0은 빈칸을 의미한다.
• 제한사항은 3 ≤ N, M ≤ 8 이다.

문제 접근

• 문제를 이해하고 난뒤 두 가지의 알고리즘을 떠올렸다. 먼저 바이러스를 퍼지게하고 안전 구역의 개수를 구하기 위해 bfs를 통해 바이러스를 퍼뜨리게한다. 
• 문제 조건에서 반드시 벽을 3개 세워야하므로 백트래킹을 이용해 벽을 3개를 세운 뒤 bfs를 통해 바이러스를 퍼지게 하면 모든 경우에 안전구역 개수의 최대값을 구할 수 있다.
• 다만 문제는 bfs를 통해 바이러스를 퍼지게 하고나면 다음 백트레킹에 지장이있다. 따라서 파이썬의 copy의 deepcopy 함수를 통해 bfs에서 사용하는 배열과 백트레킹에서 사용하는 배열을 분리시켰다.

 

정답 코드

from collections import deque
import copy

def bfs():
    q = deque()
    tmp_graph = copy.deepcopy(graph)
    # 2를 전부 퍼뜨리기 위해 2의 위치를 큐에 저장
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                q.append((i,j))
    
    while q:
        x,y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                q.append((nx,ny))

    # 안전구역 개수
    global answer
    cnt = 0
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 0:
                cnt += 1
    
    answer = max(answer, cnt)



def makWall(cnt):
    if cnt == 3:
        bfs()
        return
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makWall(cnt+1)
                graph[i][j] = 0


n, m = map(int, input().split())

graph = []

dx = [0,0,1,-1]
dy = [1,-1,0,0]

for _ in range(n):
    graph.append(list(map(int, input().split())))

answer = 0
makWall(0)
print(answer)