연구소 (14502번) - 백준 (BOJ)

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

14502번: 연구소

 

 

백준 - 연구소 (14502번)

 

난이도 : Gold 4

알고리즘&자료구조 : DFS (깊이 우선 탐색) & Combinations (조합)

 

 

from itertools import combinations as comb
from copy import deepcopy


if __name__ == '__main__':
    maxy = 0
    N, M = map(int, input().split())
    lab = [list(map(int, input().split())) for _ in range(N)]
    es, vs = [], []
    for r in range(N):
        for c in range(M):
            if lab[r][c] == 2:
                vs.append((r, c))
            elif not lab[r][c]:
                es.append((r, c))
    ini = len(es)-3
    
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    
    for walls in comb(es, 3):
        curlab = deepcopy(lab)
        for w in walls:
            curlab[w[0]][w[1]] = 1
        cur = ini
        stack = vs[:]
        while stack:
            pr, pc = stack.pop()
            for i in range(4):
                cr, cc = pr+dr[i], pc+dc[i]
                if 0 <= cr < N and 0 <= cc < M and not curlab[cr][cc]:
                    curlab[cr][cc] = 2
                    cur -= 1
                    stack.append((cr, cc))
        maxy = max(maxy, cur)
    print(maxy)

 

 

연구소 크기가 작아서,

조합으로 모든 경우의 수에 대해 구해도

시간 초과 없이 통과할 수 있었다.

 

---

 

▶ 연구소의 빈 칸들 중에서, 3개를 골라 벽을 세울 수 있는 모든 경우의 수에 대해 탐색한다.

(빈 칸 0이 n 개라면, nC3 개의 경우의 수)

 

▶ 위의 각 경우에 대해서,

초기 바이러스들 위치부터 시작해서

DFS를 통해 바이러스를 퍼트리고,

바이러스가 퍼지지 않는 빈 칸 0의 개수를 센다.

 

▶ 바이러스가 퍼지지 않는 빈 칸의 개수가 가장 많은 경우를 출력한다.