[백준 14502번] 파이썬 - 연구소

 

14502번: 연구소

 

 

# 조건

• 바이러스의 확산을 막기 위해서 연구소에 벽을 세운다.
• 연구소는 크기가 N x M
• 연구소는 빈 칸, 벽으로 이루어져 있다.
• 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
• 새로 세울 수 있는 벽의 수는 3개이며, 꼭 3개여야만 한다.
• 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
• 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하시오

 

# 접근 방법

• 브루트포스와 bfs를 이용해주면 될 것 같다.
• 벽은 무조건 3개를 이용해야 하므로 모든 조합을 구한다면 아주 많아진다.
• 따라서 벽을 세우는 조합을 최소한의 노력으로 구해준다.
• 우선, 바이러스가 있는 좌표와, 빈 좌표를 찾아서 배열에 담아주고
• 빈 좌표의 개수를 저장해준다.
• 삼중 for문을 이용하여 아까 저장해준 빈 좌표 중 3개를 골라 벽을 세우고 bfs를 진행

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import deque
from copy import deepcopy

def bfs(arr):
    global cnt
    # 원본 손상 안되게 deepcopy
    new_arr = deepcopy(arr)
    # 저장해둔 virus 리스트 q에 넣어주기
    q = deque(virus)
    new_virus = 0
    while q:
        di, dj = q.popleft()
        for i, j in move:
            ni, nj = i + di, dj+j
            if 0<=ni<N and 0<=nj<M and new_arr[ni][nj] == 0:
                q.append((ni, nj))
                # 감염 수 체크
                new_virus += 1
                # 바이러스 감염 표시
                new_arr[ni][nj] = 2

    return cnt - new_virus

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

arr = [[*map(int, input().split())] for _ in range(N)]
# 안전지대 수, 안전지역 리스트, 바이러스
# 벽 3개를 사용하므로 미리 빼준다.
cnt, safe, virus = -3, [], []
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            cnt += 1
            safe.append((i,j))

        elif arr[i][j] == 2:
            virus.append((i,j))

# 이후 벽을 세울 수 있는 모든 조합 탐색
# 실시간 카운트 변수
result = 0
move = [(1,0),(0,1),(-1,0),(0,-1)]

# 3개를 세워야 하므로 처음은 안전지대 크기 -2
# 다음 인덱스부터 안전지대 크기 -1
# 또 그다음 지역부터 마지막까지 체크
for i in range(len(safe)-2):
    for j in range(i+1, len(safe)-1):
        for k in range(j+1, len(safe)):
            # 벽을 세우는 조합
            wall = [safe[i], safe[j], safe[k]]
            for x, y in wall:
                arr[x][y] = 1
            result = max(result, bfs(arr))
            # 벽을 세워준 후 원상 복구
            for x, y in wall:
                arr[x][y] = 0

print(result)

 

깊은 복사

• 처음 코드에서는 deepcopy 모듈을 이용해줌
• 아래와 같이 리스트 컴프레션을 통해 복사해준 경우 시간이 많이 줄어드는 것을 확인할 수 있었다.

new_arr = [i[:] for i in arr]