백준 14502번 - 연구소

문제 바로가기

🙄 문제 이해

연구소에서 바이러스의 확산을 막기 위해 3개의 벽을 세우는 문제입니다.
바이러스는 빈 공간을 통해 전파되며, 벽으로 이를 막을 수 있습니다.

이를 위해선 벽을 적절한 위치에 배치해야 하며, 최대한 안전한 공간(0)을 보존해 갯수를 늘리는 것이 목표입니다.

바이러스가 전파되는 부분은 BFS를 사용할 것이라고 생각했고,
벽을 세우는 부분은 완전탐색을 통해 3개의 벽을 세워 안전 구역의 갯수를 찾으면 되겠다고 생각했습니다.

📝 문제 풀이

문제의 풀이 순서는 아래와 같습니다.

1. 조합(완전탐색)으로 3개의 벽을 배치
2. 3개의 벽을 배치한 상태에서 BFS 수행 -> 바이러스 확산
3. 바이러스 확산 후 안전 영역의 갯수 체크

입력이 작고 시간복잡도를 고려했을 때, 완전탐색으로 3개의 벽을 배치하는 부분을 3중 루프로 구성하면 될것이라고 생각했으나 구현이 잘 안돼서 조합으로 변경했습니다.

조합을 통해 3개의 벽을 배치한 후, 이 상태에서 BFS 함수를 호출해 바이러스를 확산시킵니다.
이때, 원본 맵 배열 graph을 사용하는 것이 아니라 2차원 배열을 복사한 맵 배열 vgraph를 사용해야 합니다.

바이러스 확산 시 사용하는 바이러스 큐 역시 원본을 사용하면 안되기에 복사된 큐를 사용하는데, 이 때 copy_vrs = vrs 를 해버리면 참조형 변수가 되기 때문에 vrs의 메모리 주소와 연결되어 copy_vrs를 수정하면 vrs역시 함께 수정되어 버립니다.

이를 막기 위해 copy_vrs = deque(vrs) 로 선언했습니다.

💻 Python 코드

# 백준 14502 연구소
# 조합 -> 벽세우기
# BFS -> 바이러스 확산
# 이후 0 갯수 체크해서 최댓값 갱신
from collections import deque
from itertools import combinations

def bfs(vgraph,vrs):
    copy_vrs = deque(vrs)
    visited = [[False]*m for _ in range(n)]
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    for x,y in copy_vrs:
        visited[x][y] = True

    while copy_vrs:
        x,y = copy_vrs.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m: #빈공간 바이러스 전파
                if visited[nx][ny] == False and vgraph[nx][ny] == 0:
                    vgraph[nx][ny] = 2
                    visited[nx][ny] = True
                    copy_vrs.append((nx,ny))
    return vgraph

n,m = map(int,input().split())
graph = []
empty = []
vrs = deque()
for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(m):
        if arr[j] == 2: #바이러스면 바이러스 큐에 넣음
            vrs.append((i,j))
        if arr[j] == 0: #빈 칸이면 empty 배열에 저장 -> 조합 완탐
            empty.append((i,j))

    graph.append(arr)

safe = 0
for a,b,c in combinations(empty, 3):
    #graph를 vgraph에 복사
    vgraph = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            vgraph[i][j] = graph[i][j]
    for x,y in [a,b,c]: #벽 3개 치기
        vgraph[x][y] = 1

    vgraph = bfs(vgraph,vrs)
    zero = 0
    for i in vgraph:
        for j in i:
            if j==0:
                zero += 1
    safe = max(safe, zero)
print(safe)