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

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

14502번: 연구소

Problem

• 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
• 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

조건

• 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
• 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
• 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
• 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
• 빈 칸의 개수는 3개 이상이다.

SOL

BFS/DFS의 전형적인 탐색문제 중 하나이다. 하지만, 벽을 무적권 세워야한다는 간단한 조건이 하나 더 들어가있는 형태.

 

BFS로 먼저 풀었다가, pypy3로만 통과가 되길래, python3로는 어떻게 통과가 될지 궁금해졌음.

그래서, 구글을 찾아봤고, DFS와 1차원 좌표 -> 2차원 좌표로 바꾸는 맵핑방식(반복문 1개줄임)을 이용해서 푼 풀이로 다시 제출을 해보았음!

 

문제 자체는 간단하다.

1. 세울 수 있는 벽을 세운다. (3개까지)
   • 세울 수 있는 벽은 어떻게 파악할까? => 경우의 수가 충분히 적으므로, 완전 탐색을 선택했다.
2. 바이러스를 퍼뜨린다. 
   • 바이러스를 퍼뜨릴 때, 기존의 board를 훼손 시키면 안된다. 벽을 세우는 경우를 board에 우선적으로 반영했기 때문에, 바이러스를 퍼뜨리는 board는 copy한 board여야 한다. (deepcopy 이용)
3. 안전영역을 세어준다.
   • 안전 영역을 세어주는건 2중반복에 0을 세어줘도 되지만, count라는 함수를 이용했다. (사실 똑같을거 같다)
4. 1~3 까지 과정을 반복해서, 안전영역이 제일 큰걸 도출해준다.
   • 매번 갱신하는 형태로 max(ans,area_cnt)로 구현

N,M이 커진다면?

벽을 세우는 것도, N,M이 모두 엄-청 작기 때문에, 3개를 다 세우는 완전탐색의 경우로 생각해주었다. 사실 이 경우도 N,M이 커져도 해결이 가능한 방법이 없을까 생각을 해봤는데, 마땅히 생각이 나는게 없었다.

조합의 수를 생각해줘도, n*mC3이므로,  n*m이 10000만 되도 1조인데.. 흠 더 생각해봐야할거 같다.

 

그래서, 2가지 풀이를 모두 들고와봤다.

 

DFS

import copy
import sys
input = sys.stdin.readline

dx =[0,1,0,-1]
dy =[1,0,-1,0]
N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
area=0
virus=[]
#print(board)
#바이러스의 위치는 변함이 없다.
for i in range(N):
    for j in range(M):
        if board[i][j] ==2:
            virus.append((i,j))

def wall(start,count):
    global area
    if count==3:
        tmp_board=copy.deepcopy(board)
        #bfs 식으로 , deque에 넣어주면, 그 다음 board에선 바이러스 위치가 없기 때문에,
        #아래와 같이 구현했다.
        for num in range(len(virus)):
            y,x = virus[num]
            solve(y,x,tmp_board)
        area_cnt = sum(tmp.count(0) for tmp in tmp_board)
        area= max(area,area_cnt)
    else:
    	#반복문 1개를 줄였음.
        for i in range(start,N*M): 
            y=i//M
            x=i%M
            #backtracking과 비슷하지 않나?
            if board[y][x] ==0:
                board[y][x] =1 
                wall(i,count+1)
                board[y][x] =0

def solve(y,x,tmp_board):
    if tmp_board[y][x] ==2:
        for k in range(4):
            ny =y+dy[k]
            nx= x+dx[k]
            if (0<=ny<N and 0<=nx<M) and tmp_board[ny][nx] ==0:
                tmp_board[ny][nx] =2
                solve(ny,nx,tmp_board)
                
wall(0,0)
print(area)

 

BFS

#연구소
#바이러스를 막아라 + + 
from collections import deque
import copy
import sys
input = sys.stdin.readline

dx=(0,1,0,-1)
dy=(1,0,-1,0)
N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]

ans=0


def select_wall(cnt):
    if cnt==3:
        bfs()
        return
    else:
        for i in range(N):
            for j in range(M):
                if board[i][j]==0:
                    board[i][j] =1
                    select_wall(cnt+1)
                    board[i][j] =0

def bfs():
    virus = deque()
    tmp_board=copy.deepcopy(board)
    for i in range(N):
        for j in range(M):
            if tmp_board[i][j] ==2:
                virus.append((i,j))
    global ans
    while virus:
        y,x= virus.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<M) and tmp_board[ny][nx] ==0:
                tmp_board[ny][nx] =2
                virus.append((ny,nx))
    area= sum(tmp.count(0) for tmp in tmp_board)
    ans= max(ans,area)


select_wall(0)
print(ans)