[백준] 14502.연구소

📌문제

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

🎖️난이도

✔️풀이

from itertools import combinations
from collections import deque
import copy

def getDim(graph, two_xy_list, pos_list, n, m):
    # 벽 3곳 세우기
    G = copy.deepcopy(graph) # 받아온 graph 그대로 쓰면 얕은 복사 돼서 X! (원본에 영향끼침)
    for i in range(3):
        x, y = pos_list[i]
        G[x][y] = 1
    
    # 감염 시작 (bfs)
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    for two_pos in two_xy_list:
        queue = deque([two_pos])

        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if nx in range(0, n) and ny in range(0, m):
                    if G[nx][ny] == 0:
                        G[nx][ny] = 2
                        queue.append([nx, ny])

    # 안전 면적 구하기
    cnt = 0
    for i in range(n):
        for j in range(m):
            if G[i][j] == 0:
                cnt+=1

    return cnt


# main
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
zero_xy_list = [] # 0인 좌표들
two_xy_list = [] # 2인 좌표들
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            zero_xy_list.append([i, j])
            continue
        if graph[i][j] == 2:
            two_xy_list.append([i, j])
            continue

xy_list = [[a, b, c] for a,b,c in combinations(zero_xy_list, 3)] # 벽 3개 조합들

max_dim = 0
for trio in xy_list:
    max_dim = max(max_dim, getDim(graph, two_xy_list, trio, n, m)) # 최대 면적 구하기

print(max_dim)

🧠노트

범위가 3에서 8정도밖에 안되고, 세워야 하는 벽의 개수도 딱 3개로 정해져 있으니까
요정도 상황에서는 combinations (64C3) 다 구해도 됨! (brute-force)

3개의 벽을 세울 수 있는 모든 경우의 수를 다 구하고 (xy_list)
각 경우마다 안전 영역의 면적을 구해서 그 중 max를 구하면 된다.

1. 우선 벽 3곳을 세우고 (1로 치환)
2. 바이러스 감염 시킨 후 (모든 2부터 시작점으로 해서 각각 bfs)
3. 0에 해당하는 남은 안전 영역의 면적을 구해주면 된다. (getDim 끝!)

이때, 핵심은 얕은 복사(매개변수 그냥 이용)가 아닌 깊은 복사(copy.deepcopy)를 해야 한다는 것!

🔍참고

cf. 얕은 복사 vs 깊은 복사

[Python] 얕은 복사🥵 vs 깊은 복사🤗