[BOJ] 14502번 - 연구소

14502번: 연구소

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

문제 정의

---

연구실의 바이러스 확산을 막기 위해 연구소에 벽을 세워야 한다. 연구소는 N*M 인 직사각형이고 1*1의 정사각형으로 나뉘어있다고 가정한다.

연구소는 빈 칸, 벽으로 이루어져 있는데 일부 칸은 바이러스가 존재한다.

0이라면 빈 칸, 1이라면 벽, 2는 바이러스가 존재함을 나타낸다.

이 때 안전한 영역 크기의 최댓값을 구해야 한다.

벽은 꼭 3개만 사용할 수 있다.

접근 방법

---

안전 영역은 벽이 세워져서 빈 칸으로 남을 수 있는 ‘0’의 개수를 세면 된다.

가장 최댓값의 0의 개수를 찾아서 결과를 출력하면 된다.

일단, 벽 3개가 세워질 위치 3곳을 정해야 하는데 이것은 ‘완전탐색’으로 접근했다. 어차피 N과 M의 크기가 크지 않으니 python의 조합(combinations) 라이브러리를 사용해서 가능한 조합을 구했다.

각 경우의 수 마다 벽을 세우고 바이러스를 퍼뜨리면 된다. 이 때는 2의 상하좌우에 바이러스를 퍼뜨리면 되므로 BFS를 활용했다.

마지막으로 최종 그래프에서 0의 개수를 세면 된다.

문제 해설

---

• empty 리스트에 벽이 세워질 수 있는 공간, 즉 현재 0인 위치의 인덱스를 저장한다.

• combinations을 사용하여 empty 리스트에서 3개의 조합 경우의 수를 만든다.

• 각 조합을 돌면서, 그 조합에 따라 그래프에 벽을 세운다.

• 이 때 오리지널 그래프 정보인 graph의 값을 보존하기 위해 새로운 변수인 safe_graph를 생성하고, graph의 정보를 복사하기 위해 python의 copy.deepcopy 함수를 사용한다.

• 벽을 세우고 난 뒤, bfs 함수를 사용해 바이러스를 퍼뜨린다.

• 각 조합마다 카운트 했던 0의 개수 리스트 중 가장 큰 값을 출력한다.

풀이

---

# 벽의 개수는 3개, 꼭 3개를 세워야 한다.
# 안전영역: 0의 개수
# 안전 영역 크기의 최댓값을 구하는 프로그램.
# 2(바이러스), 1(벽), 0(빈 칸)

import sys
import copy
from itertools import combinations
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())    # 세로, 가로 -> (3 ≤ N, M ≤ 8)
graph = []  # 연구소 정보
for _ in range(N):
    graph.append(list(map(int, input().split())))

# 1을 3개 넣고(완전탐색?) -> 바이러스 퍼지게 한 뒤(그래프 탐색) => 0의 개수를 센다.

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

def bfs(safe_graph, a, b):
    queue = deque()
    queue.append((a, b))
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:  # 범위 조심(N, M을 반대로 쓰지 말자)
                continue
            if safe_graph[nx][ny] == 1:  # 벽이라면 퍼지지 못하므로 패스
                continue
            if safe_graph[nx][ny] == 0:
                safe_graph[nx][ny] = 2
                queue.append((nx, ny))
    
    return

# 1. 0의 위치를 기억하기
empty = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            empty.append((i, j))

# 2. 벽을 세워보기
cnt_list = []   # 0의 개수가 담긴 리스트

combs = combinations(empty, 3)  # ex) ((0, 0), (0, 1), (0, 2))
for c in combs:
    cnt = 0     # 0의 개수
    safe_graph = copy.deepcopy(graph)
    
    for idx in c:   # 3번 반복
        safe_graph[idx[0]][idx[1]] = 1
    
    # 바이러스 퍼지는 단계 - 그래프를 탐색하면서 2의 상하좌우를 검사하면서 퍼뜨린다.
    for i in range(N):
        for j in range(M):
            if safe_graph[i][j] == 2:    # 현재 위치에 바이러스가 있다면,
                bfs(safe_graph, i, j)    # 상하좌우에 퍼뜨린다.
                
    # 3. 0의 개수 세기
    for i in range(N):
        for j in range(M):
            if safe_graph[i][j] == 0:
                cnt += 1
    cnt_list.append(cnt)

print(max(cnt_list))

정리

---

• 알고리즘으로, 완전탐색/그래프탐색-bfs가 동시에 나온 문제였다.

• 시간 복잡도는 계산해보니 $O(N^3)$ 같기도..? 하다.

• 아이디어를 떠올리기에는 쉬운 문제였다. 더 빨리 풀려면 bfs를 좀 더 능숙하게 다룰 줄 알아야 한다.

Uploaded by N2T