[BOJ] 14502 - 연구소

문제

이 문제는 3가지 절차로 나눌 수 있다 1)벽 만들기 2)감염 3)안전 영역 크기 구하기

초기 설정

from collections import deque
import copy
import sys
input = sys.stdin.readline
 
N, M = tuple(map(int, input().strip().split(' ')))

lab = []
for _ in range(N):
    row = list(map(int, input().strip().split(' ')))
    lab.append(row)

벽 만들기

def make_wall(count):
    if count == 3:
        infect()
        return
    for i in range(N):
        for k in range(M):
            if lab[i][k] == 0:
                lab[i][k] = 1
                make_wall(count+1)
                lab[i][k] = 0

3가지 벽을 세우는 모든 경우의 수를 고려해야 하기 때문에, 재귀함수를 사용해 모든 경우의 수를 거치게 한다.
벽을 3개 세우게 되면 infect() 함수를 실행해 감염을 시작한다.

감염

def infect():
    q = deque()
    test_lab = copy.deepcopy(lab)
    for i in range(N):
        for s in range(M):
            if test_lab[i][s] == 2:
                q.append((i,s))

    while q:
        i,s = q.popleft()

        for d in range(4):
            ny = i+dy[d]
            nx = s+dx[d]

            if (0<= ny < N) and (0<= nx < M) and test_lab[ny][nx] == 0:
                test_lab[ny][nx] = 2
                q.append((ny, nx))

감염을 시킬 때 값이 2인 칸에서 4방향으로 계속 퍼져나가기 때문에 DFS가 아닌 BFS(넓이 우선 탐색)을 사용해 감염시킨다.

3개의 벽을 세운 모든 lab의 경우를 고려해야 하기 때문에, 같은 Lab의 좌표를 계속 변형시키기보단 하나의 경우를 고려할 때 고유의 lab을 확인하는 것이 좋기 때문에 deepcopy해준다.

deque에 값이 2인 값을 전부 넣고, deque에서 popleft한 좌표(처음)에서 4방향으로 뻗어나간 좌표들 중 조건에 맞는 좌표들을 deque에 append(뒤에 배치) 시켜준다.

이런 방식을 계속 반복해나가면 감염시킬 수 있는 좌표들은 전부 감염시키게 된다.

안전 영역 크기 구하기

		global result
    count = 0
    for i in range(N):
        for k in range(M):
            if test_lab[i][k] == 0:
                count +=1

    result = max(result, count)

하나의 경우를 고려할 때마다 infect() 함수 내에서 구한 값(Local)과 result값(global)을 계속 비교해주어야 하기 때문에 global로 선언하고 비교한다.

전체코드

from collections import deque
import copy
import sys
input = sys.stdin.readline
 
N, M = tuple(map(int, input().strip().split(' ')))

lab = []
for _ in range(N):
    row = list(map(int, input().strip().split(' ')))
    lab.append(row)

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

def infect():
    q = deque()
    test_lab = copy.deepcopy(lab)
    for i in range(N):
        for s in range(M):
            if test_lab[i][s] == 2:
                q.append((i,s))

    while q:
        i,s = q.popleft()

        for d in range(4):
            ny = i+dy[d]
            nx = s+dx[d]

            if (0<= ny < N) and (0<= nx < M) and test_lab[ny][nx] == 0:
                test_lab[ny][nx] = 2
                q.append((ny, nx))

    global result
    count = 0
    for i in range(N):
        for k in range(M):
            if test_lab[i][k] == 0:
                count +=1

    result = max(result, count)
    

def make_wall(count):
    if count == 3:
        infect()
        return
    for i in range(N):
        for k in range(M):
            if lab[i][k] == 0:
                lab[i][k] = 1
                make_wall(count+1)
                lab[i][k] = 0

result = 0 
make_wall(0)
print(result)