[백준] 14502 연구소 [Python]

문제 링크 : https://www.acmicpc.net/problem/14502

14502번: 연구소

 

---

풀이과정

이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 

 

우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다.

 

배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중에 출력해주는 식으로 구현을 합니다.

 

---

 

    N,M = map(int,s.readline().split())
    arr= [list(map(int,s.readline().split()))for _ in range(N)]
    
    result=0
    count=0
    
    #네 방향 탐색을 위한 변수설정
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    
    wall(0)

 

위의 코드는  문제에서 주어진 기본 입력 및 네 방향 탐색을 위한 dx,dy 변수 설정을 합니다. 그리고 벽의 개수를 세는 함수인 wall함수를 호출해줍니다.

 

 

#벽을 세우고 벽의 개수가 3이되면 bfs실행
def wall(count):
    if count==3:
        bfs()
        return
    for i in range(N):
            for j in range(M):
                if arr[i][j]==0:
                    arr[i][j]=1
                    wall(count+1)
                    arr[i][j]=0

 

 

위의 코드는 벽의 개수를 세서 3개가 됐을때 bfs를 실행하는 함수이고 이중 for문을 통해서 백트래킹으로 모든 경우의 수를 탐색하는 함수입니다.

 

 

 

def bfs():
    global result
    global count
    q=deque()
    test_map = copy.deepcopy(arr)
    
    #바이러스 위치 q에 저장
    for i in range(N):
        for j in range(M):
            if test_map[i][j]==2:
                q.append((i,j))
            
    #바이러스를 모든 칸에 전염시키는과정        
    while q:
        x,y = q.popleft()
        
        for i in range(4):    
            nx = x+dx[i]
            ny = y+dy[i]
            
            if 0<=nx<N and 0<=ny<M and not test_map[nx][ny]:
                q.append((nx,ny))
                test_map[nx][ny]=2
    
    #바이러스 전염 후 안전영역의 개수 카운트하기
    count=0
    # for i in range(N):
    #     for j in range(M):
    #         if test_map[i][j]==0:
    #             count+=1
    for i in range(N):
        count += test_map[i].count(0)
    #안전영역 최대개수 저장
    result=max(result,count)

 

 

위의 코드는 bfs함수의 구현부분입니다. 우선 배열을 저장해둔 arr를 바꾸면 경우의 수마다 계속 초기화를 시켜줘야하기때문에 arr를 copy해서 새로운 테스트용 배열을 만들어줍니다.

 

새로운 테스트용 배열로 경우의 수마다 안전 영역의 개수를 구하고 모든 부분을 탐색했으면 다시 다음 경우의 수로 넘어갈때 테스트 배열도 다시 copy하기 때문에 매번 초기화해줄 필요가 없어집니다.

 

이 문제는 백트래킹, 브루트포스 알고리즘을 사용하기때문에 시간이 오래 걸릴 수 밖에 없습니다. 모든 범위를 다 탐색하면 result변수에 저장해둔 값을 출력해주면 됩니다.

 

 

전체코드

from sys import stdin as s
from collections import deque
import copy
s=open('input.txt','rt')


def bfs():
    global result
    global count
    q=deque()
    test_map = copy.deepcopy(arr)
    
    #바이러스 위치 q에 저장
    for i in range(N):
        for j in range(M):
            if test_map[i][j]==2:
                q.append((i,j))
            
    #바이러스를 모든 칸에 전염시키는과정        
    while q:
        x,y = q.popleft()
        
        for i in range(4):    
            nx = x+dx[i]
            ny = y+dy[i]
            
            if 0<=nx<N and 0<=ny<M and not test_map[nx][ny]:
                q.append((nx,ny))
                test_map[nx][ny]=2
    
    #바이러스 전염 후 안전영역의 개수 카운트하기
    count=0
    # for i in range(N):
    #     for j in range(M):
    #         if test_map[i][j]==0:
    #             count+=1
    for i in range(N):
        count += test_map[i].count(0)
    #안전영역 최대개수 저장
    result=max(result,count)


#벽을 세우고 벽의 개수가 3이되면 bfs실행
def wall(count):
    if count==3:
        bfs()
        return
    for i in range(N):
            for j in range(M):
                if arr[i][j]==0:
                    arr[i][j]=1
                    wall(count+1)
                    arr[i][j]=0
if __name__=='__main__':
    N,M = map(int,s.readline().split())
    arr= [list(map(int,s.readline().split()))for _ in range(N)]
    
    result=0
    count=0
    
    #네 방향 탐색을 위한 변수설정
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    
    wall(0)
    print(result)