[백준/파이썬] #14502: 연구소

문제

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

14502번: 연구소

 

풀이

1. 벽 세우기 -> make_wall 함수

: 재귀 호출 이용하여 0만날때 값을 1로 변경 -> count 증가 -> 밖으로 나올 때 다시 0으로 -> 벽 3개다 세우면 bfs호출

2. 바이러스 퍼뜨리기 & 안전영역 크기 재기-> dfs 함수

: 상하좌우 움직일 수 있게끔 d 변수 생성

- queue 만들어 map deepcopy -> 바이러스 퍼진 곳을 queue에 넣기. 

 - 좌표값 확인하며 상하좌우 움직이면서 바이러스 퍼진 곳 2로 변경 -> queue에 좌표 넣기

- 바이러스 다 퍼뜨린 후, 퍼지지 않은 곳(빈칸) 개수 세고, 최대 안전지대 개수(result) 도출하기

3. 안전지대 개수인 result 출력하기

 

코드

from collections import deque
import copy
import sys
input = sys.stdin.readline

d = [[-1,0],[1,0],[0,-1],[0,1]]

def bfs():
    queue = deque()
    test_map = copy.deepcopy(lab_map)
    for i in range(n):
        for k in range(m):
            if test_map[i][k] == 2:
                queue.append((i,k))

    while queue:
        r,c = queue.popleft()

        for i in range(4):
            dr = r+d[i][0]
            dc = c+d[i][1]

            if (0<=dr<n) and (0<=dc<m):
                if test_map[dr][dc] == 0:
                    test_map[dr][dc] =2
                    queue.append((dr,dc))

    global result
    count = 0
    for i in range(n):
        for k in range(m):
            if test_map[i][k] == 0:
                count +=1

    result = max(result, count)


def make_wall(count):
    if count == 3:
        bfs()
        return
    for i in range(n):
        for k in range(m):
            if lab_map[i][k] == 0:
                lab_map[i][k] = 1
                make_wall(count+1)
                lab_map[i][k] = 0


n, m = map(int,input().split())
lab_map = [list(map(int,input().split())) for _ in range(n)]

result = 0
make_wall(0)

print(result)