[백준] 14502 - 연구소 (Python)

들어가며

우왕,,,,,
brute force 나의 아픈 손가락ㅎ
재귀, dp, 브루트 포스 문제를 많이 많이 풀어봐야겠다.

이 문제의 포인트

1. deepcopy
2. 재귀로 벽 3개를 만드는 과정

이리봐도 저리봐도 맞왜틀,,,
하지만 deepcopy를 하지 않아 오류가 날 수 밖에 없었다.
새로운 벽 조합이 생길 때마다 함수로 들어가야하니 말이다.

나의 코드

import copy,sys
input = sys.stdin.readline

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
safe_area = 0

## 3. 바이러스 퍼짐 & 안전영역 갯수 쳌
def virus():
    global safe_area

    #### 매번 검사를 해줘야하기 때문에 딥카피 필수~~
    n_arr = copy.deepcopy(arr)
    queue = copy.deepcopy(virus_location)
   
    ## 바이러스 퍼뜨리기
    while queue:
        x, y = queue.pop(0)

        for d in range(4):
            nx = x + dr[d]
            ny = y + dc[d]

            if 0 <= nx < n and 0 <= ny < m:
                if n_arr[nx][ny] == 0:
                    n_arr[nx][ny] = 2
                    queue.append((nx, ny))

    # 안전영역 갯수 쳌
    ### 이중 for문으로 쳌하면 시간초과~~~~~
    cnt = 0
    for i in n_arr:
        cnt += i.count(0)
    safe_area = max(cnt, safe_area)

## 1. 바이러스 위치를 담아 줌, 꼭 deepcopy 사용하기!! 
virus_location = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            virus_location.append((i,j))

## 2. 벽을 선택하고 바이러스를 퍼뜨림
def walls(wall_cnt):
    if wall_cnt == 3:
        virus()
        return
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                arr[i][j] = 1
                walls(wall_cnt+1)
                arr[i][j] = 0
walls(0)


print(safe_area)

쉽지만 어려운 문제였다.