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

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

14502번: 연구소

• 이 문제는 제가 다른 bfs 문제(토마토, 바이러스 문제 등등..)와 비슷한 줄 알고 풀지 않았지만 문제를 잘 읽어보니 완전 탐색 + bfs를 사용해야 할 것 같아서 풀어본 문제입니다.
• 먼저 최종적으로 구해야 하는 건 안전영역 지대 즉, 벽 3개를 세우고(1을 3개를 배치하고) 난 뒤의 0의 개수를 구하면 되는 문제이므로 바이러스가 얼만큼 퍼졌는지를 확인해 줘야 합니다.
• 바이러스는 그냥 일반적인 bfs로 풀어주면 되고, 추가되어야 할 부분은 0의 개수가 가장 많을 때의 결과값을 max_result에 저장해두면서 갱신해주는 구현입니다.
• 그럼 이 bfs 함수를 언제 돌려줘야하나?
  브루트 포스로 벽 3개를 둘 수 있는 모든 경우의 수를 구해주고 그때마다 bfs함수를 돌려줘야 안전영역 최댓값을 구해줄 수 있습니다.
• 추가적으로 첫 번째 코드는 deepcopy를 이용해서 그 bfs함수를 실행할 때마다 새로운 temp graph에 입력받은 graph를 복사해서 구현했고, 두 번째 코드는 deepcopy를 없애고, 안전영역 개수로만 구현해준 코드입니다.
  두 번째 코드가 deepcopy를 안써서 시간이 더 적게 걸렸습니다.

import sys,copy
from collections import deque

input = sys.stdin.readline


dx = [1,-1,0,0]
dy = [0,0,1,-1]

n,m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

max_result = 0
# dfs함수안에서 퍼지는 바이러스의 수를 구할 bfs함수
def virus():
    global max_result
    temp = copy.deepcopy(graph)
    result = 0
    q = deque()
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                q.append((i,j))
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <=ny < m:
                if temp[nx][ny] == 0:
                    temp[nx][ny] = 2
                    q.append((nx,ny))
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                result += 1
    # dfs함수안에서는 안전영역 max 값( 2의 개수 최솟값)을 갱신해야한다.             
    max_result = max(max_result,result)

# 1 3개로 벽을 세우는 경우의 수를 구하는 dfs 함수
def wall_dfs(cnt):
    if cnt == 3:
        virus()
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wall_dfs(cnt+1)
                graph[i][j] = 0
wall_dfs(0)
print(max_result)

                                                                                                                                                        

import sys,copy
from collections import deque

input = sys.stdin.readline


dx = [1,-1,0,0]
dy = [0,0,1,-1]

n,m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            cnt += 1 #처음0의개수
max_result = 0
# dfs함수안에서 퍼지는 바이러스의 수를 구할 bfs함수
def virus():
    visited = [[0] * m for _ in range(n)]
    global max_result
    # print(graph)
    # graph = copy.deepcopy(graph)
    result = 0
    q = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2:
                visited[i][j] = 1
                q.append((i,j))
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <=ny < m and visited[nx][ny]==0:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 1
                    # graph[nx][ny] = 2
                    result += 1
                    q.append((nx,ny))
    # for i in range(n):
    #     for j in range(m):
    #         if graph[i][j] == 0:
    #             result += 1
    # dfs함수안에서는 안전영역 max 값( 2의 개수 최솟값)을 갱신해야한다.             
    max_result = max(max_result,cnt-result)

# 1 3개로 벽을 세우는 경우의 수를 구하는 dfs 함수
def wall_dfs(cnt):
    if cnt == 3:
        virus()
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wall_dfs(cnt+1)
                graph[i][j] = 0
wall_dfs(0)
print(max_result-3)