[이코테] DFS/BFS_연구소 (python) (푸는중)

문제

나의 풀이

1. 실패: 왜 틀렸는지 모름

# 1. 벽 3개를 세우는 모든 경우의 수. 벽이 다 세워지면 바이러스가 퍼진다
def wall(cnt):
    if cnt == 3:
        virus(cnt, arr, 0, 0)
        return
    for x in range(n):
        for y in range(n):
            if arr[x][y] == 0:
                arr[x][y] == 1
                wall(cnt + 1)
                arr[x][y] == 0
# 2. 바이러스가 퍼졌을 때 안전영역의 크기
def virus(cnt, arr, x, y):
    global max_cnt
    for g in go:
        next_x, next_y = (x + g[0]), (y + g[1])
        if (0 <= next_x < n) and (0 <= next_y < m):
            if arr[next_x][next_y] == 0:
                arr[next_x][next_y] = 2
                virus(cnt, arr, next_x, next_y)
	
    for c in range(n):
        cnt += arr[c].count(0)
    max_cnt = max(max_cnt, cnt)
    return
n, m = map(int, input().split()) # n: 행, m: 열
arr_real = [list(map(int, input().split())) for _ in range(n)] # 연구소 list
arr = [x[:] for x in arr_real]
cnt, max_cnt = 0, 0
go = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
max_cnt = 0
wall(0)
print(max_cnt)

2. 실패! 시간 초과에 메모리 초과까지..

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

# 1. 바이러스가 퍼지는 함수
def virus(arr, x, y):
    for a, b in go:
        next_x, next_y = x + a, y + b
        if 0 <= next_x < n and 0 <= next_y < m:
            if arr[next_x][next_y] == 0:
                arr[next_x][next_y] = 2
                virus(arr, next_x, next_y)
                    
# 2. 안전영역의 크기를 구하는 함수       
def safty(result):               
    for r in range(n):
        result += arr[r].count(0)
    return result

n, m = map(int, input().split()) # n: 행, m: 열
arr_real = [list(map(int, input().split())) for _ in range(n)] # 연구소 list
arr = [[0] * m for _ in range(n)] # 사용할 list    
            
answer = 0
go = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우

# 3. 벽 3개를 세우는 모든 경우의 수. 벽이 다 세워지면 바이러스가 퍼지고, 안전영역의 크기를 잰다.
def wall(cnt):
    global answer
    if cnt == 3:
        for i in range(n):
            for j in range(m):
                arr[i][j] = arr_real[i][j]
        for i in range(n):
            for j in range(m):
                if arr[i][j] == 2: # 바이러스가 존재하면, 확산
                    virus(arr, 0, 0)
        answer = max(answer, safty(0))
        return answer
    
    for x in range(n):
        for y in range(n):
            if arr_real[x][y] == 0:
                arr_real[x][y] == 1
                wall(cnt + 1)
                arr_real[x][y] == 0 # 초기화
                cnt -= 1

wall(0)

• ^^..미치것다 시간 초과에 메모리 초과에 아주 풍년이구나

3. combinations 이용중

from itertools import combinations
# 1. 벽의 개수가 3인 경우: combination으로 구하기
def wall(labs):
    labs_copy = [lab[:] for lab in labs]
    labs_zero = [(x, y) for x in range(n) for y in range(m) if labs[x][y] == 0]
    lab_wall = combinations(labs_zero, 3)
    
    
    
    return labs

# 2. 바이러스가 퍼짐
def virus(labs):
    # 우선, 2차원 list 복사(깊은복사)
    # 이때, deepcopy를 사용해도 되지만, 엄청 느림
    labs_2 = [lab[:] for lab in labs]
    
    for lab in labs_2:
        
    
# 3. 안전지대 count
def safe():
    
n, m = map(int, input().split())
labs = []
for _ in range(n):
    lab = map(int, input().split())
    labs.append(lab)