그래프 탐색 - 백준 14502 연구소 바이러스

 

문제

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

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

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

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

 

해설 

1. DFS vs BFS ?

상관 없다. 바이러스를 퍼트릴 때 사용될 예정인데, 모든 벽이 아닌 노드를 방문할 수 있으면 된다. 

 

 

 

import copy
from collections import deque

# BFS로 바이러스 퍼트리기
def spread_virus(lab, n, m):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상, 하, 좌, 우
    queue = deque()
    
    # 바이러스 위치 큐에 추가
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 2:
                queue.append((i, j))
    
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and lab[nx][ny] == 0:
                lab[nx][ny] = 2  # 바이러스 퍼트리기
                queue.append((nx, ny))

# 안전 영역 계산
def get_safe_area(lab, n, m):
    safe_area = 0
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0:
                safe_area += 1
    return safe_area

# 벽 세울 곳을 찾는 함수
def build_wall(count, lab, n, m):
    if count == 3: # 벽이 3개라면, 더 이상 세울 곳을 찾지 않고 끝냄
        lab_copy = copy.deepcopy(lab)
        spread_virus(lab_copy, n, m) # 바이러스를 뿜어냄
        return get_safe_area(lab_copy, n, m) # 안전영역 개수를 찾아서 반환
    
    max_safe_area = 0
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0:  # 빈 공간에 벽 세우기
                lab[i][j] = 1 # 
                max_safe_area = max(max_safe_area, build_wall(count + 1, lab, n, m))
                lab[i][j] = 0  # 벽 되돌리기 
    return max_safe_area 

# 입력 처리
n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]

# 벽이 0개인 상황부터 시작
result = build_wall(0, lab, n, m)
print(result)