[백준] 14502: 연구소 python 구현 / bfs

문제

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

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

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

 

자세한 문제는 링크에서 !

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

14502번: 연구소

 

풀이

1. 벽을 세운다.
   1. 벽을 세울 수 있는 빈방(0)에서 중복을 포함한 2개의 후보군들을 리스트로 만듦
   2. 후보군 리스트에서 3가지를 combination으로 추출 ( 순서상관이 없기 때문에 순열x )
2. 바이러스를 퍼뜨린다
   1. queue에 바이러스를 담고 확산시킨다. - BFS
3. 안전 구역의 개수를 센다.
4. 최대값과 비교하여 이를 바꿔치기 한다.

중요한점 ! 

• 모든 벽의 후보군을 돌면서 이를 수행해야하기 때문에, 처음 입력받은 laboratory변수를 직접 사용하지 않고 deepcopy하여 사용한다. 이때 사용하는 python의 copy 라이브러리 

import copy
a = [1, 2, 3]
b = copy.deepcopy(a)

이렇게 사용하면 b를 변경하여도 a가 변경되지 않는다.

 

CODE

import sys
from collections import deque
import itertools
import copy

n, m = map(int, input().split())
laboratory = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치
# 2 <= n(2)<= 10, n(3) >= 3

# 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다

# 벽의 조합 구하기
def get_wall_list(n, m):
    wall_candidate = []
    for i in range(n):
        for j in range(m):
            if laboratory[i][j] == 0:
                wall_candidate.append((i, j))

    # candidate 중에서 3개를 뽑아야 함 (순서 상관x) -> combinations
    return list(itertools.combinations(wall_candidate, 3))

# 바이러스 퍼뜨리기
def bfs(queue):
    while queue:
        x, y = queue.popleft()

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

            if nx<0 or ny<0 or nx>(n-1) or ny>(m-1): continue
            if vst[nx][ny]: continue

            # 빈방이라면 바이러스를 확산 시킨다.
            if not lab[nx][ny]:
                lab[nx][ny] = 2
                queue.append((nx, ny))
                vst[nx][ny] = 1

            if lab[nx][ny] in [1, 2]:
                vst[nx][ny] = 1

def safe_zone(x, y):
    safe_coor = deque()
    safe_coor.append((x, y))
    safe_vst[x][y] = 1

    lab[x][y] = 1
    safe_cnt = 1

    while safe_coor:
        x, y = safe_coor.popleft()

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

            if nx<0 or ny<0 or nx>(n-1) or ny>(m-1): continue
            if safe_vst[nx][ny]: continue

            if not lab[nx][ny]:
                safe_cnt += 1
                lab[nx][ny] = 1

                safe_vst[nx][ny] = 1
                safe_coor.append((nx, ny))
            else:
                safe_vst[nx][ny] = 1
    
    return safe_cnt

v_vst = [[0]*m for _ in range(n)]

# 바이러스의 위치를 queue에 넣음
v_queue = deque()
for i in range(n):
    for j in range(m):
        if laboratory[i][j] == 2:
            v_queue.append((i, j))
            v_vst[i][j] = 1

max_safe_cnt = 0
# 벽의 조합을 구하고
wall_comb = get_wall_list(n, m)
for walls in wall_comb:
    lab = copy.deepcopy(laboratory)
    
    # 1. 벽 세우기
    for w1, w2 in walls:
        lab[w1][w2] = 1
    
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    # 2. 바이러스 확산 시키기
    queue = copy.deepcopy(v_queue)
    vst = copy.deepcopy(v_vst)
    bfs(queue)
    
    # 안전 구역 개수 세기
    safe_vst = [[0]*m for _ in range(n)]
    sum_safe_cnt = 0
    for sx in range(n):
        for sy in range(m):
            if lab[sx][sy] == 0:
                safe_cnt = safe_zone(sx, sy)
                sum_safe_cnt += safe_cnt
    if sum_safe_cnt > max_safe_cnt:
        max_safe_cnt = sum_safe_cnt

print(max_safe_cnt)