백준 14502 연구소

문제

연구소

벽을 세워 안전 영역 최대값을 구하자

난이도 : Gold4

---

풀이

1. 벽을 세울 수 있는 경우를 완전탐색한다.
2. dfs를 이용해 바이러스를 전파시키고, 0의 개수를 구한다.

---

코드

import sys
import itertools
from copy import deepcopy
from collections import deque

n, m = list(map(int, sys.stdin.readline().split()))
data = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False for _ in range(m)] for _ in range(n)]

zeros = [(i, j) for i in range(n) for j in range(m) if data[i][j] == 0]  # 벽을 세울 수 있는 좌표들
infect_points = [(i, j) for i in range(n) for j in range(m) if data[i][j] == 2]  # 감염 시작(2) 좌표 리스트

zero_cases = list(itertools.combinations(zeros, 3))  # 벽을 세울 수 있는 가능한 모든 조합

def security_zone(d):  # 2차원 리스트에서 0(안전 영역)의 개수를 구한다.
    cnt = 0
    for i in range(n):
        for j in range(m):
            if d[i][j] == 0:
                cnt += 1
                
    return cnt

def dfs(change_data, points, visit):
    for point in points:
        queue = deque([point])
        # dfs시작
        while queue:
            tup = queue.popleft()
            c, r = tup[0], tup[1]
            for i in range(4):           
                nc = c + direction[i][0]
                nr = r + direction[i][1]
                if 0 <= nc < n and 0 <= nr < m:
                    if not visit[nc][nr]:
                        visit[nc][nr] = True
                        if change_data[nc][nr] == 0:
                            change_data[nc][nr] = 2
                            queue.append((nc, nr))
        
    return security_zone(change_data)  # 바이러스가 전파된 data를 security zone 함수를 이용해 안전 영역 크기를 return

infection = []
for zero in zero_cases:
    data_copy = deepcopy(data)  # 깊은 복사를 이용해 완전 탐색에 이용
        
    for z in zero:  
        data_copy[z[0]][z[1]] = 1  # 벽 생성
    
    visited = [[False for _ in range(m)] for _ in range(n)]
    infection.append(dfs(data_copy, infect_points, visited))

print(max(infection))

        

---

결과