백준 알고리즘 No.14502 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
(중략)
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
체감 난이도: ★★
DFS와 BFS를 완벽히 이해하고 있다면 쉽게 풀릴 듯 하다..
생각보다는 어렵지 않았으나 왠지 더 좋은 풀이가 있을 것 같다는 생각이 든다.
Code
import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations
import copy
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
def bfs(tmp_lab):
queue = deque()
for i in range(x):
for j in range(y):
if tmp_lab[i][j] == 2:
queue.append((i, j))
while queue:
virus_x, virus_y = queue.popleft()
for i in range(4):
infection_x = virus_x + d[i][0]
infection_y = virus_y + d[i][1]
if (0 <= infection_x < x) and (0 <= infection_y < y):
if tmp_lab[infection_x][infection_y] == 0:
tmp_lab[infection_x][infection_y] = 2
queue.append((infection_x, infection_y))
global result
count = 0
for i in range(x):
for j in range(y):
if tmp_lab[i][j] == 0:
count += 1
result = max(result, count)
def make_wall_combinations():
wall_combinations = combinations(empty, 3)
for walls in wall_combinations:
tmp_lab = copy.deepcopy(lab)
for wall in walls:
tmp_lab[wall[0]][wall[1]] = 1
bfs(tmp_lab)
x, y = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(x)]
empty = [(i, j) for i in range(x) for j in range(y) if lab[i][j] == 0]
result = 0
make_wall_combinations()
print(result)
Solution (Combinations 활용)
우선 나는 조합을 활용해 풀었지만, 재귀를 활용해 푸는 방식도 있다.
하지만 실험 결과, 조합을 활용하는 방식이 더 빠르다.
bfs 함수
✔ virus 좌표 큐에 삽입
d = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 바이러스가 퍼질 영역 (상하좌우)
def bfs(tmp_lab):
queue = deque() # bfs 탐색할 것이므로 큐로 받아온다.
for i in range(x):
for j in range(y):
if tmp_lab[i][j] == 2: # 전체 바이러스 좌표 큐에 삽입
queue.append((i, j))
bfs(tmp_lab)함수는 바이러스를 bfs 탐색하여 퍼뜨리고 안전 영역의 최대 크기를 계산하는 함수d리스트로 바이러스가 퍼질 영역 설정 (상하좌우)- 우선 바이러스를 퍼뜨리기 위해 바이러스 좌표들을
queue에 삽입한다.
✔ bfs 탐색을 활용하여 주변 좌표 감염 시키기
while queue:
virus_x, virus_y = queue.popleft() # 바이러스 좌표 꺼내오기
for i in range(4): # 상하좌우 반복 (감염 좌표 설정)
infection_x = virus_x + d[i][0]
infection_y = virus_y + d[i][1]
if (0 <= infection_x < x) and (0 <= infection_y < y): # 맵을 벗어나지 않고,
if tmp_lab[infection_x][infection_y] == 0: # 빈칸이라면,
tmp_lab[infection_x][infection_y] = 2 # 감염 작업
queue.append((infection_x, infection_y)) # 다음 레벨 탐색을 위해 큐에 삽입
- 큐에 있는 바이러스 좌표 중 먼저 추가된 좌표부터
popleft()를 통해 꺼낸다. - 그 다음,
d리스트를 활용해virus좌표의 상하좌우 좌표 값을infection좌표에 넣는다. - 만약
infection좌표가 전체 맵을 벗어나지 않고, 빈칸(0)이라면, 감염시킨(2로 변경) 후 큐에 삽입한다.
✔ 안전 영역의 최대 크기 계산
global result
count = 0
for i in range(x):
for j in range(y):
if tmp_lab[i][j] == 0: # 안전 영역 개수 세기
count += 1
result = max(result, count) # 최댓값 업데이트
count의 초기값을 설정하고, 빈칸(안전 영역)의 개수를 센다.max(result, count)를 통해 최댓값을 계속해서 업데이트 한다.
make_wall 함수
✔ 벽을 3개 세우는 경우의 수 탐색
def make_wall_combinations():
wall_combinations = combinations(empty, 3)
for walls in wall_combinations:
tmp_lab = copy.deepcopy(lab)
for wall in walls:
tmp_lab[wall[0]][wall[1]] = 1
bfs(tmp_lab)
combinations함수를 활용해empty에서 3개의 좌표를 선택한 조합들을 만들어준다.- 각 조합에 대해
tmp_lab을 복사한 후, 해당 좌표에 벽을 세운 다음bfs(tmp_lab)함수를 호출한다.
입력 받기
x, y = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(x)]
empty = [(i, j) for i in range(x) for j in range(y) if lab[i][j] == 0]
result = 0
make_wall_combinations()
print(result)
- 입력으로 주어진 연구실의 크기와 상태를 받아온다.
empty리스트를 생성하여 초기 상태에서 값이 0인 좌표를 저장한다.make_wall_combinations()함수를 호출하여 벽을 세우는 모든 경우의 수를 탐색하고 최대 안전 영역의 크기를 받아온다.
Solution 2 (Recursion 활용)
시간 초과!! PyPy3는 통과 가능
import sys
input = sys.stdin.readline
from collections import deque
import copy
d = [[-1,0], [1,0], [0,-1], [0,1]]
def bfs(): # 위의 코드와 동일
queue = deque()
tmp_lab = copy.deepcopy(lab)
for i in range(x):
for j in range(y):
if tmp_lab[i][j] == 2:
queue.append((i, j))
while queue:
virus_x, virus_y = queue.popleft()
for i in range(4):
infection_x = virus_x + d[i][0]
infection_y = virus_y + d[i][1]
if (0 <= infection_x < x) and (0 <= infection_y < y):
if tmp_lab[infection_x][infection_y] == 0:
tmp_lab[infection_x][infection_y] = 2
queue.append((infection_x, infection_y))
global result
count = 0
for i in range(x):
for j in range(y):
if tmp_lab[i][j] == 0:
count += 1
result = max(result, count)
def make_wall_recursion(count):
if count == 3: # 벽이 3개라면 bfs 함수 호출
bfs()
return
for i in range(x):
for j in range(y): # 전체 그래프를 탐색하면서
if lab[i][j] == 0: # 빈칸이라면
lab[i][j] = 1 # 벽 세우기
make_wall_recursion(count+1) # 다음 벽 세우기 (재귀 호출)
lab[i][j] = 0 # 벽 허물기 (백트래킹)
x, y = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(x)]
result = 0
make_wall_recursion(0)
print(result)
- 벽이 3개가 되면
bfs()함수를 호출하고 호출 스택에서 현재 함수 호출 종료- 이전 단계로 돌아가면서, 마지막으로 세운 벽을 허물고 다음 빈 칸 탐색 (백트래킹)
- 재귀를 통해 반복하면서 모든 경우의 수 탐색
혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃
