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가 동시에 나온 문제였다.
- 시간 복잡도는 계산해보니 같기도..? 하다.
- 아이디어를 떠올리기에는 쉬운 문제였다. 더 빨리 풀려면 bfs를 좀 더 능숙하게 다룰 줄 알아야 한다.
Uploaded by N2T
