백준 14502
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값 구하기.
- 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
- 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
- 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
- 이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
- 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
- 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
- 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
- 빈 칸의 개수는 3개 이상이다.
입출력
| 입력 | 출력 |
|---|---|
| 7 7 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 | 27 |
| 4 6 0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2 | 9 |
| 8 8 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 3 |
접근 방식
: 1. 벽 3개를 세운다.
2. 바이러스를 퍼뜨린다.
3. 안전영역을 구한다.
4. 안전영역의 최댓값을 구한다.
이렇게 완전탐색으로 푸는 문제임을 알게되었다.
문제는 벽3개를 어떻게 세울것이냐?
알게된 점
- 벽 세우기
- 재귀
- 벽이 3개가 될때까지 재귀함수 호출
- 조합
- 입력받은 배열에서 값이 0인 인덱스를 따로 리스트에 저장한다. 그 리스트로 3개씩 조합을 만든다. 그 조합에 대해 벽을 세우고 안전영역을 구한다.
copy
: import copy. 새로운 리스트를 만들어서 기존 리스트를 할당해버리면 동일한 메모리를 가리키기 때문에 독립적으로 사용 x.
ex. b가 a의 레퍼런스를 가져가면 a가 바뀌는 순간 b도 바뀐다.
---> 리스트를복사함으로써 해결할 수 있음.
- 얕은 복사 copy : 리스트에서 [:]와 동일
- 깊은 복사 deepcopy : 이차원 이상일 때
코드
재귀
from collections import deque
import copy
import sys
n, m = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
maxi = -1e9
# 바이러스 퍼뜨리고 안전영역 카운트
def bfs(copyArr):
global maxi
result = 0
q = deque()
for i in range(n):
for j in range(m):
if copyArr[i][j]==2:
q.append((i, j)) # 숙주 위치 큐에 삽입
dx = [-1,1,0,0]
dy = [0,0,-1,1]
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 copyArr[nx][ny] == 0:
copyArr[nx][ny] = 2
q.append((nx, ny))
for i in range(n): # 안전영역
for j in range(m):
if copyArr[i][j] == 0:
result += 1
maxi = max(maxi, result) # 안전영역 크기 업데이트
# 벽 세우기
def wall(cnt):
if cnt == 3: # 벽이 3개가 되면
copyArr = copy.deepcopy(maps) # 3개 세운 리스트 복사해서 넘기기
bfs(copyArr)
return
for i in range(n):
for j in range(m):
if maps[i][j] == 0:
maps[i][j] = 1
wall(cnt+1)
maps[i][j] = 0
wall(0)
print(maxi)
- pypy로 제출
조합
from collections import deque
from itertools import combinations
import copy
import sys
n, m = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
maxi = -1e9
# 바이러스 퍼뜨리고 안전영역 카운트
def bfs(copyArr):
global maxi
result = 0
q = deque()
for i in range(n):
for j in range(m):
if copyArr[i][j]==2:
q.append((i, j)) # 숙주 위치 큐에 삽입
dx = [-1,1,0,0]
dy = [0,0,-1,1]
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 copyArr[nx][ny] == 0:
copyArr[nx][ny] = 2
q.append((nx, ny))
for i in range(n): # 안전영역
for j in range(m):
if copyArr[i][j] == 0:
result += 1
maxi = max(maxi, result) # 안전영역 크기 업데이트
# 벽 세우기
def wall():
zeros = []
for i in range(n):
for j in range(m):
if maps[i][j] == 0:
zeros.append((i, j))
combi = list(combinations(zeros, 3))
for c in combi:
copyArr = copy.deepcopy(maps)
copyArr[c[0][0]][c[0][1]] = 1
copyArr[c[1][0]][c[1][1]] = 1
copyArr[c[2][0]][c[2][1]] = 1
bfs(copyArr)
wall()
print(maxi)