[백준/Python] #14502 연구소

문제

 

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

14502번: 연구소

---

Algorithm

1. 배열 A를 입력받을 때 상하좌우를 탐색하기 편하게 하기 위해 가장자리의 바깥부분에 1을 추가한다.

2. 선언된 A 중에서 A[i][j] == 0인 (i, j)에 대한 집합 Z를 생성한다.

3. A를 복사한 B에 대해 Z 중 3개를 골라 그 (i, j)에 해당하는 B의 값을 1로 바꾼다.

4. dfs로 상하좌우에 0인 부분을 찾아서 그 부분을 2로 바꿔가며 2로 바뀐 0의 개수 x를 구한다. 이때 시작점은 B에서 2에 해당하는 위치이다.

5. combination을 이용해 위의 3~4의 과정을 반복하며 x의 최솟값을 구한다.

6. 안전영역이란 0의 개수를 의미하므로 2에서 선언한 Z의 길이에서 1로 바꾼 0의 개수 3을 빼고 다시 이 값에서 2로 바뀐 0의 최솟값 x를 뺀다.

6에서 얻은 값이 정답이 된다.

 

---

 

 

Code

import sys
from itertools import combinations as cb

input = sys.stdin.readline

def dfs(idx : tuple, A : list):
    i, j = idx
    A[i][j] = 2
    V[i - 1][j - 1] = True

    area = 0
    for n, m in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:
        if A[n][m] == 0:
            if V[n - 1][m - 1] == False:
                area += dfs((n, m), A) + 1
    
    return area

N, M = map(int, input().split())
V = [[False] * M for _ in range(N)]
array = [[1] * (M + 2)] + [[1] + list(map(int, input().split())) + [1] for _ in range(N)] + [[1] * (M + 2)]

zeros = []
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if array[i][j] == 0:
            zeros.append((i, j))

area = len(zeros)
ans = area + 1
for (a, b), (c, d), (e, f) in cb(zeros, 3):
    A = [array[i][:] for i in range(N + 2)]
    A[a][b] = 1
    A[c][d] = 1
    A[e][f] = 1
    s = 0
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if A[i][j] == 2:
                if V[i - 1][j - 1] == False:
                    s += dfs((i, j), A)
    if s <= ans:
        ans = s
    V = [[False] * M for _ in range(N)]

print(area - 3 - ans)