[백준] 14502번 - 연구소 (파이썬) 문제 및 풀이

문제) 백준 - 너비 우선 탐색(BFS) - 연구소

- 14502번: 연구소 (acmicpc.net)

14502번: 연구소

 

벽과 바이러스가 아닌 모든 지역(space)을 탐색해 벽의 후보(wall_candidates)를 골라 준다. combinations를 이용해 조합을 만들어주고 원본을 유지하기 위해 deepcopy를 이용해 복사 후 벽을 세워 bfs로 탐색해준다. 그 후 각 조합마다 안전 지역 개수의 최댓값을 구한다.

 

 

완전 탐색으로 접근하면 쉽게 풀리는 문제이지만 처음에 그리디하게 접근해서 헤맸던 문제.

 

 

소스 코드)

from itertools import combinations
from collections import deque
from copy import deepcopy
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if temp[nx][ny] == 1:
                continue
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                queue.append((nx, ny))

def count_safe_zone(a:list):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if a[i][j] == 0:
                cnt += 1
    return cnt


n, m = map(int,input().split())
space = []
graph = []

for i in range(n):
    line = list(map(int, input().split()))
    for j in range(m):
        if line[j] == 0:
            space.append((i, j))
    graph.append(line)

wall_candidates = list(combinations(space, 3))
safe_zone = 0

for wall_candidate in wall_candidates:
    temp = deepcopy(graph)

    for point in wall_candidate:
        temp[point[0]][point[1]] = 1

    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                bfs(i, j)

    safe_zone = max(safe_zone, count_safe_zone(temp))


print(safe_zone)