연구소 (백준 14502번)

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

14502번: 연구소

 

문제를 풀 때 벽을 어떤 규칙으로 세워야 최대 크기의 안전 영역을 구할 지 매우 고민했던 문제이다. 한참을 고민해도 마땅한 규칙이 생각나지 않아서  '이거 그냥 일일히 벽 세워보고 안전영역 세어봐야 하는거 아냐?' 라고 생각했었는데... 그게 정답이었다...

 

이 문제에서 주어지는 맵의 크기도 8x8이고, 벽을 세울 수 있는 모든 조합의 수는 64C3 이기에, 이는 100,000 보다도 작은수이다. 시간제한이 2초인걸 감안했을 때 충분히 제한 시간안에 해결 할 수 있다. 따라서 벽을 개수가 3개가 되는 모든 조합을 찾아서 그 안에서 탐색 알고리즘으로 계산하면 된다!

 

키포인트는 벽을 3개 다 세우고 바이러스를 퍼트려 그 때 안전영역을 계산한후, 제일 먼저 세웠던 벽을 지우고 다른 위치에 벽을 다시 세우는 것이 중요하다.

 

아래 메서드가 그 역할을 한다. 

def wall(cnt):
    if cnt == 3:
        spread_virus()
        return
    
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                matrix[i][j] = 1
                wall(cnt+1)
                matrix[i][j] = 0

 

전체 코드는 다음과 같다.

import sys
from collections import deque
import copy


n, m = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
res = []

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


# 너비 우선 탐색으로 바이러스를 퍼트린다.
# 바이러스를 퍼트린 후, 몇개인지 센다.
def spread_virus():
    q = deque()
    temp_map = copy.deepcopy(matrix)
    cnt = 0

    for i in range(n):
        for j in range(m):
            if temp_map[i][j] == 2:
                q.append((i, j))

    while q:
        cx, cy = q.popleft()

        for dir in range(4):
            nx = dx[dir] + cx
            ny = dy[dir] + cy

            if 0 <= nx < n and 0 <= ny < m:
                if temp_map[nx][ny] == 0:
                    temp_map[nx][ny] = 2
                    q.append((nx, ny))


    for i in range(n):
        for j in range(m):
            if temp_map[i][j] == 0:
                cnt += 1

    res.append(cnt)

# 벽을 세우는 메서드
# 벽을 3개를 세웠다면 바이러스를 퍼트리고 안전영역을 센다.
# 결과를 리스트에 넣고 제일 먼저 세웠던 벽을 지우고 다시 벽을 세운다.
def wall(cnt):
    if cnt == 3:
        spread_virus()
        return
    
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                matrix[i][j] = 1
                wall(cnt+1)
                matrix[i][j] = 0
wall(0)

print(max(res))