[백준] 14502 연구소 (Python 파이썬)

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

14502번: 연구소

문제 설명

N x M 크기로 구성된 연구소에 바이러스가 퍼졌다.

연구소의 각 칸은 0, 1, 2로 구성되어 있으며 0은 빈 칸, 1은 벽, 2은 바이러스 이다.

바이러스는 벽을 뚫고 확장할 수 없으며 상하좌우에 인접한 빈 칸으로만 확장이 가능하다.

위 그림과 같이 N x M 모양의 연구소(행렬)가 주어지며, 3개의 벽(1)을 세워야 한다.

3개의 벽을 세웠을 때, 안전영역의 크기(0의 개수)의 최댓값을 구하면 된다.

---

풀이 과정

바이러스는 '2' 이며 상하좌우의 인접한 빈칸(0)으로만 이동이 가능하기 때문에

먼저 '2'인 칸들을 모두 큐에 넣어준 후에,

BFS(너비우선탐색)을 통해 큐에서 하나씩 꺼내 확장시키는 방식으로 진행하면 된다.

 

2인 칸에서 시작하여 주변의 0인 칸들을 2로 만드는 방식이다.

 

이 때, 어디에 벽을 세워야 최댓값이 나올지는 알 수 없기 때문에 벽을 세울 수 있는 모든 경우의 수에 대해 수행해봐야 한다.

따라서, (1, 1) 칸 부터 (n, m)칸 까지 중 빈칸을 순서대로 하나씩 3개 선택하여

벽을 세우고 BFS를 수행한 후 벽을 지우고

그 다음칸에 대해 다시 벽을 세우고 BFS를 수행하고 벽을 지우는 방식을 반복해야 한다.

즉, 백트래킹 방식을 이용해 3개의 벽을 모든 칸에 세워본다.

 

이렇게 진행하면서 최댓값을 저장한 후, 모든 탐색이 끝난 후 최댓값을 출력하면 된다.

 

이를 파이썬으로 나타낸 코드는 다음과 같다.

from collections import deque
import copy

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

    while queue:
        x, y = queue.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
                queue.append((nx, ny))

    global answer
    cnt = 0

    for i in range(n):
        cnt += tmp_graph[i].count(0)

    answer = max(answer, cnt)


def makeWall(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
                makeWall(cnt+1)
                graph[i][j] = 0

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

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

answer = 0
makeWall(0)
print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !