[백준] 14502번: 연구소 with Python

BOJ 14502

• DFS
• Brute Force

문제

---

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

풀이과정

---

입력으로 주어지는 행렬의 최대 크기는 8x8이다. 최악의 경우 탐색해야하는 모든 경우의 수 64C3은 41,664로, 문제의 시간 제한인 2초 이내에 완전탐색으로 풀이가 가능하다고 보고 Brute Force와 DFS로 문제풀이를 진행했다. Backtracking으로도 경우의 수를 줄여 해결할 수 있다고 하는데, 아직 잘 모른다...

파이썬의 itertools에는 리스트에서 n개의 값의 조합을 추출할 수 있는 combinations 이라는 함수가 존재한다.

from itertools import combinations

combinations([a, b, c, d], 3)

위와 같이 코드를 작성하면 [a,b,c], [a,b,d], [b,c,d]가 함수의 실행결과로 나오게 된다. 입력받은 연구소 정보에서 빈 칸의 좌표를 찾고, 그 영역의 조합을 계산하여 가능한 모든 경우의 수를 탐색 했다.

바이러스가 퍼져나가는 과정은 DFS로 구현했는데 현재 좌표에 바이러스가 있을 경우 (arr[x][y] == 2), 상하좌우로 바이러스가 퍼져나가도록 구현했다. 단, 벽으로 막혀있거나 이미 바이러스가 존재한다면 바이러스가 퍼져나가지 않으므로 각 좌표가 빈 칸인 경우에만 (arr[x][y] == 0) 퍼져나가도록 했다.

코드

---

from itertools import combinations
from copy import deepcopy

# 0: 빈 칸, 1: 벽, 2: 바이러스, 2이상 10미만
dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]

# N: 세로, M: 가로
N, M = map(int, input().split())

W = 3    # 벽의 수

# 배열 입력
arr = []
for i in range(N):
    arr.append(list(map(int, input().split())))


def cnt_sf(_arr):
    _cnt = 0
    for _i in range(N):
        for _j in range(M):
            if _arr[_i][_j] == 0:
                _cnt += 1
    return _cnt


def virus_spread(x, y):
    # if virus then spread
    if arr[x][y] == 2:
        # spread recursively
        for dx, dy in zip(dxs, dys):
            nx = x + dx
            ny = y + dy
            # in range
            if 0 <= nx < N and 0 <= ny < M:
                # if not spread before and empty space
                if arr[nx][ny] == 0:
                    # spread
                    arr[nx][ny] = 2
                    virus_spread(nx, ny)

                    
empty_space = []    # empty space
for i in range(N):
    for j in range(M):
        # possible wall space
        if arr[i][j] == 0:
            empty_space.append((i, j))

# possible wall zone
pos = combinations(empty_space, W)
answer = 0
tmp = deepcopy(arr)

for state in pos:
    arr = deepcopy(tmp)
    # build new wall
    for x, y in state:
        arr[x][y] = 1

    # virus spread
    for i in range(N):
        for j in range(M):
            virus_spread(i, j)
    answer = max(answer, cnt_sf(arr))
    
print(answer)