[백준 파이썬] 14502번 연구

[백준 파이썬] 14502번 연구

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 

연구소의 크기는 N x M인 직사각형으로 나타낼 수 있으면 1X1 정크기의 정사각형으로 나누어져 있다.

연구소는 빈칸과 벽칸으로 이루어져 있다.

 

바이러스는 인접한 상화좌우로 퍼져나갈 수 있다.

벽을 세워서 바이러스가 퍼지는걸 막아야 하는데 세울 수 있는 벽의 개수는 3개이면 꼭 3개만 세워야 한다.

이때 바이러스가 퍼지지 않은 빈칸의 개수가 최대가 되는 값을 구하여라.

 

입력

첫줄에 연구소의 세로 N과 가로 M이 주어진다

그다음줄부터 N줄에 지도의 모양이 주어진다. 

0은 빈칸 1은 벽 2는 바이러가 있는 위치이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

풀이

BFS와 백트래킹을 이용하여 문제를 풀었다.

벽을 3개를 세워야함으로 벽을 세우는 모든 경우의 수를 탐색할 수 있도록 백트래킹을 이용한다.

벽을 세우고 BFS로 탐색하고 탐색이 끝나면 0의 개수를 비교하고 그 후 세운 벽을 허물고 다시 새로운 위치에 벽을 세우고

BFS 탐색하고 0의 개수를 비교하는 이 과정을 반복하여 벽을 세울 모든 경우의 탐색한 후 0의 개수가 최대인 값을 출력하면 된다.

이 방법은  해보지는 않았지만 조합을 이용해서도 풀 수 있지 않을까 한다.

 

 

코드

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

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


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


#바이러스 확장 하고 값 돌려받기 
def bfs():
    global ans

    q=deque()
    temp=copy.deepcopy(array)

    for i in range(n):
        for j in range(m):
            if temp[i][j]==2:
                q.append((i,j))
    while q:
        x,y=q.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]

            if nx>=0 and nx<n and ny>=0 and ny<m:
                if temp[nx][ny]==0:
                    temp[nx][ny]=2
                    q.append((nx,ny))
    # for i in range(n):
    #     print(temp[i])
    # a=int(input())

    cnt=0
    for i in range(n):
        for j in range(m):
            if temp[i][j]==0:
                cnt+=1
    ans=max(cnt,ans)
    

        
#벽 모든 경우수 확인하기
def wall(count):

    if count==3:
        bfs()

        return 
    for i in range(n):
        for j in range(m):
            if array[i][j]==0:
                array[i][j]=1
                wall(count+1)
                array[i][j]=0

wall(0)
print(ans)

결과

파이썬으로 돌리면 시간초과가 나타나고 PYP3로 돌려야 통과가 된다.