[#14502] 연구소

RookieAND·2022년 6월 2일

BFS 백준 코테

BaekJoon

목록 보기

9/42

❓ Question

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

📖 Before Start

브루트 포스와 BFS 탐색을 적절히 활용하여 풀어야 하는 문제처럼 보였다.

이번 문제는 기본적으로 BFS를 사용하되, 브루트 포스 방식으로 해결을 봐야 하는 문제였다.
처음엔 더 나은 방법이 없을까 고민도 많이 했는데, 일단은 내 식대로 풀어야겠다는 생각이 들었다.

✒️ Design Algorithm

벽을 총 3개 세워야 하는데, 그럼 벽을 세우는 좌표를 어떻게 선별해야 할까?

N * M 이차원 배열 내에서, 0 은 빈 공간을 의미하고, 1 은 벽, 2 는 바이러스를 의미한다.
바이러스는 상하좌우 에 인접한 빈 공간으로 퍼져나갈 수 있고, 벽을 뚫고 지나갈 수는 없다.
연구소의 도안이 주어졌을 때, 가장 큰 안전 공간 (바이러스가 없는) 의 사이즈를 구해야 한다.

3개의 가벽 을 세우기 위한 좌표 3개를, 빈 공간 중에서 랜덤하게 추출해보자.

입력 받은 이차원 배열 중에서, 빈 공간인 0 이 든 좌표 (X, Y) 를 별도의 리스트에 저장한다.
그 후, 조합 (Collections) 을 사용하여 전체 빈 공간 좌표 중에서 3개를 무작위하게 뽑아온다.
가벽을 세운 후, BFS 탐색을 통해 바이러스를 최대한 퍼트린 후 남은 안전 공간의 크기를 구한다.
기존에 저장되었던 안전 공간의 최댓값과 비교하여, 값이 더 크다면 변수를 업데이트 한다.

💻 Making Own Code

✅ Correct Code

import sys, copy
from collections import deque
import itertools as iters

read = sys.stdin.readline
N, M = map(int, read().split())

graph = [list(map(int, read().split())) for _ in range(N)]
empty_place = []

# 연구소 내에서 빈 공간의 좌표를 추출하는 파트 (Y, X)
for row in range(N):
    for col in range(M):
        if graph[row][col] == 0:
            empty_place.append((row, col))


# 바이러스가 퍼질 수 있는 네 방향에 대한 2차원 벡터를 저장.
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]


# BFS 탐색을 통해 인접한 빈 공간에 바이러스를 퍼트리는 함수
def virus_spread(y, x):
    queue = deque([(y, x)])
    temp_graph[y][x] = 2
    while queue:
        ny, nx = queue.popleft()
        for direct in direction:
            my = ny + direct[0]
            mx = nx + direct[1]
            # 이동한 좌표가 유효 범위 내에 있고, 아직 빈 공간인지를 판별
            if (0 <= my < N and 0 <= mx < M) and not temp_graph[my][mx]:
                temp_graph[my][mx] = 2
                queue.append((my, mx))


# 바이러스가 전부 퍼진 후, 연구실 내의 안전 공간의 크기를 구하는 함수.
def get_safety_area():
    size = 0
    for row_list in temp_graph:
        size += row_list.count(0)
    return size


max_size = 0
# 전체 빈 공간에서, 무작위하게 3곳을 선택하여 벽을 세움.
for loc_list in iters.combinations(empty_place, 3):
    # 벽을 세운 후의 연구소 모양을 deepcopy로 깊은 복사하여 가져옴.
    temp_graph = copy.deepcopy(graph)
    # 랜덤으로 선택된 좌표 세 곳에 벽을 새롭게 세움.
    for loc in loc_list:
        y, x = loc
        temp_graph[y][x] = 1

    # 연구소 공간을 순회하면서, 바이러스가 있다면 주변 영역을 감염시킴.
    for i in range(N):
        for j in range(M):
            if temp_graph[i][j] == 2:
                virus_spread(i, j)

    # 감염이 진행된 후, 빈 공간을 구하여 최댓값과 비교함
    size = get_safety_area()
    max_size = max(max_size, size)

print(max_size)