[Gold IV] 연구소 - 14502

문제 링크

성능 요약

메모리: 36068 KB, 시간: 1580 ms

분류

너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색, 구현

문제 설명

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

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

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0

1 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 1 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2

1 0 1 0 1 2 2

0 1 1 0 1 2 2

0 1 0 0 0 1 2

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

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

---

문제 풀이

문제 분석

이 문제는 연구소 지도가 주어졌을 때, 지도 내 빈 칸에 벽 3개를 세워서 바이러스가 퍼지는 것을 막고, 안전 영역의 최대 크기를 구하는 문제입니다. 지도는 N x M 크기의 2차원 배열로 주어지며, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치를 나타냅니다. 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나갑니다.

접근 방법

이 문제는 브루트 포스(완전 탐색)와 BFS(너비 우선 탐색)를 결합하여 해결할 수 있습니다.

1. 벽 세우기 (브루트 포스): 가능한 모든 벽의 조합(빈 칸 중에서 3개를 선택하는 조합)을 생성합니다.
2. 바이러스 확산 (BFS): 각 벽 조합에 대해, 바이러스를 BFS를 사용하여 확산시킵니다.
3. 안전 영역 계산: 바이러스가 모두 확산된 후, 안전 영역(바이러스가 퍼지지 않은 빈 칸)의 크기를 계산합니다.
4. 최대값 갱신: 모든 벽 조합에 대해 안전 영역 크기를 계산하고, 최대 안전 영역 크기를 갱신합니다.

구현 설명

1. 입력 및 초기 설정

• 지도의 크기 N, M을 입력받고, 지도를 2차원 배열 graph에 저장합니다.
• 바이러스의 위치를 저장하는 queue 리스트와 빈 칸의 위치를 저장하는 wall 리스트를 생성합니다.

2. 벽 조합 생성 및 시뮬레이션

• wall 리스트에서 3개의 위치를 선택하는 모든 조합을 combinations 함수를 사용하여 생성합니다.
• 각 벽 조합에 대해 다음 단계를 수행합니다.
  • 선택된 3개의 위치에 벽을 세웁니다 ( graph 값을 1로 변경).
  • BFS 함수를 호출하여 바이러스 확산을 시뮬레이션하고, 안전 영역 크기를 계산합니다.
  • 벽을 다시 제거합니다 ( graph 값을 0으로 변경). 이 과정은 다른 벽 조합에 영향을 주지 않도록 보장합니다.
  • 계산된 안전 영역 크기를 result 리스트에 추가합니다.

3. BFS 함수

• BFS 함수는 주어진 그래프, 크기, 바이러스 위치, 그리고 결과를 저장할 리스트를 인자로 받습니다.
• 방문 여부를 체크하기 위한 visited 2차원 배열을 생성합니다.
• 입력받은 queue를 복사한 queue2를 생성하고, queue2를 사용하여 BFS를 수행합니다.
• 각 바이러스 위치에서 상하좌우 인접한 칸을 탐색하며, 빈 칸이고 방문하지 않은 칸을 queue2에 추가합니다.
• BFS가 완료된 후, 방문하지 않은 빈 칸의 개수를 계산하여 안전 영역 크기를 구하고, result 리스트에 추가합니다.

4. 결과 출력

• result 리스트에서 최대값을 찾아 출력합니다. 이 값은 얻을 수 있는 최대 안전 영역 크기입니다.

⏱복잡도 분석

• 시간 복잡도:

  • 빈 칸의 개수를 K라고 할 때, 벽을 세울 수 있는 조합의 수는 O(K^3)입니다. (K는 최대 N*M)
  • 각 조합에 대해 BFS를 수행하며, BFS의 시간 복잡도는 O(N*M)입니다.
  • 따라서, 전체 시간 복잡도는 O(K^3 * N*M) = O((N*M)^4)입니다. N과 M이 최대 8이므로 실행 가능한 시간 내에 계산이 완료됩니다.

• 공간 복잡도:

  • 지도를 저장하는 graph 배열: O(N*M)
  • BFS 방문 여부를 저장하는 visited 배열: O(N*M)
  • 빈 칸의 위치를 저장하는 wall 리스트: O(N*M)
  • 따라서, 전체 공간 복잡도는 O(N*M)입니다.

핵심 포인트

1. 브루트 포스 + BFS 결합: 문제의 제약 조건(N, M <= 8)을 활용하여 모든 벽 조합을 시도하고, 각 조합에 대해 BFS를 사용하여 바이러스 확산을 시뮬레이션하는 효율적인 접근 방식을 사용합니다.
2. BFS를 위한 visited 배열: BFS를 수행할 때 방문 여부를 체크하는 visited 배열을 사용하여 중복 방문을 방지하고, 효율적인 탐색을 보장합니다.
3. 벽 설치 및 제거: 각 벽 조합에 대해 벽을 설치한 후 BFS를 수행하고, 다음 조합을 위해 벽을 다시 제거하는 과정을 통해 독립적인 시뮬레이션을 수행합니다. 이는 다른 벽 조합에 영향을 주지 않도록 합니다.

풀이 코드

from itertools import combinations
from collections import deque
import sys

def BFS(graph,n,m,queue,result):
    visited = [[False] * m for _ in range(n)]
    queue2 = deque(queue[:])
    for x, y in queue2:
        visited[x][y] = True

    direction = [(0,1),(0,-1),(1,0),(-1,0)]
    while queue2:
        x,y = queue2.popleft()
        for sx,sy in direction:
            dx,dy = sx+x,sy+y
            if 0<=dx<n and 0<=dy<m and graph[dx][dy] == 0 and visited[dx][dy] == False:
                visited[dx][dy] = True
                queue2.append([dx,dy])
    count=0
    for i in range(n):
        for j in range(m):
            if visited[i][j] == False and graph[i][j] == 0:
                count+=1
    result.append(count)

n,m = map(int,sys.stdin.readline().split())

graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

wall = []
queue = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            queue.append([i,j])
        elif graph[i][j] == 0:
            wall.append([i,j])

wall_graph = combinations(wall,3)
result = []
for walls in wall_graph:
    graph[walls[0][0]][walls[0][1]] = 1
    graph[walls[1][0]][walls[1][1]] = 1
    graph[walls[2][0]][walls[2][1]] = 1
    BFS(graph,n,m,queue,result)
    graph[walls[0][0]][walls[0][1]] = 0
    graph[walls[1][0]][walls[1][1]] = 0
    graph[walls[2][0]][walls[2][1]] = 0

print(max(result))