[이것이 코딩 테스트다 with Python] Chapter 13. DFS/BFS - 연구소

< 연구소 >

 

💬 문제 설명

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

....

 

입력	출력
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

💬 입력 조건

• 첫째 줄에 지도의 세로 크기 N, 가로 크기 M ( 3 ≤ N, M ≤ 8 )
  
• 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. ( 0은 빈칸, 1은 벽, 2는 바이러스)
• ( 2 ≤ 바이러스의 개수 ≤ 10)
• 빈 칸의 개수는 3개 이상

💬 출력 조건

• 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력

---

✍ 문제요약

주어지는 2차원 배열의 입력에 통로(0) , 벽(1), 바이러스(2) 가 존재한다. 바이러스는 상하좌우로 퍼져나갈 수 있고 바이러스가 퍼져 나가지 않은 지역을 안전영역이라 칭한다. 총 3개의 벽을 무조건 세워야 할 때, 안전영역이 최대가 되는 경우의 최댓값을 구하라.

💯 문제링크

백준14502 문제와 동일하다.

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

14502번: 연구소

---

✅  문제 풀이

• 통로에서 3개의 벽을 고르는 모든 경우를 확인해야 한다고 생각했다.
• N과 M의 크기가 작기 때문에 브루트포스 알고리즘이 가능할 것이다.
• 3개의 벽을 세웠다는 가정하에, 바이러스 위치에 대한 BFS 알고리즘을 적용했다.

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

def BFS(virus, safe):
    Q = deque(virus)           # 바이러스 좌료를 deque로 변경 (BFS를 위해서)
    area = safe                # 현재 안전영역 수
    
    # 벽을 세우는 한 경우에 대한 방문표시 2차원 배열 생성
    vi = [[1 if G[n][m] == 1 else 0 for m in range(M)] for n in range(N)]
    for r, c in walls: vi[r][c] = 1
    for r, c in Q : vi[r][c] = 2

    while Q:
        r, c = Q.popleft()
        for dr, dc in ((0, 1),(1, 0),(0, -1),(-1, 0)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < M and not vi[nr][nc]: # vi에서 통로인 경우에
                Q.append((nr,nc))                              # 바이러스 이동 
                vi[nr][nc] = 1                                 # 방문표시
                area -= 1                                      # 현재 안전영역 수 -1
                if Max >= area : return 0                      # 안전영역의 수가 최댓값보다 낮아지면 중단
    return area                                                # 그렇지 않으면 최댓값 업데이트

N, M = map(int,input().split())
virus, roads, G = [], [], []      # 바이러스좌표, 통로좌표
safe, Max = -3, 0                 # 벽을 3개 세웠을 때 안전영역 갯수

for r in range(N):                # 2차원배열 생성과 동시에 virus, roads 좌표 저장
    tmp = list(map(int,input().split()))
    G.append(tmp)
    for c in range(M):
        if tmp[c] == 2 : virus.append((r,c)) ;
        elif tmp[c] == 0 : roads.append((r,c)) ; safe += 1  # 현재 안전영역 확인

for walls in combinations(roads,3):  # 3개의 벽을 세울 통로 조합으로 선정
    Max = max(Max, BFS(virus, safe))

print(Max)

• 완전탐색이기 때문에 전체적으로 오래 걸리지만, 그렇게 느린편은 아닌것 같다.