[dfs,bfs/백준] 14502번: 연구소

- 문제 : https://www.acmicpc.net/problem/14502

 

이번이 세번째 풀이인데도 막히는 부분이 똑같아서 이번에는 세밀하게 코드를 분석해보려고 한다 

참고로 pypy3으로 돌려야 시간초과가 안 발생한다 

 

로직 

1. 벽(1) 3개를 설치하기 

2. 벽 설치가 완료되면 2인 지점을 찾아서 바이러스 전파 -> bfs()를 통해 구현

3. 바이러스 전파 완료되면 0의 갯수 셈 -> get_num()을 통해 구현 

 

순서

-벽 설치 완료? 

if count ==3:

data 복사

for i in range(n):
	for j in range(m):
    	temp[i][j]=data[i][j]

2인 지점찾고, 바이러스 전파 

for i in range(n):
	for j in range(m):
    	if temp[i][j]==2:
        	bfs(i,j)

전파 완료되면 0의 갯수 세기

answer=max(answer,get_num())

def get_num():
	num=0
    for i in range(n):
    	for j in range(m):
        	if temp[i][j]==0:
            	num+=1
	return num

-완료가 안됐으면, 벽 세우기 

for i in range(n):
	for j in range(m):
    	if data[i][j]==0:
        	data[i][j]=1
            count+=1
            dfs(count)
            #다른 경우도 진행해야하므로 값 초기화 
            data[i][j]=0
            count-=1

 

- 정답 풀이 :

from collections import deque

n,m=map(int,input().split())
data=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=0
temp=[[0]*m for _ in range(n)]

for i in range(n):
    data.append(list(map(int,input().split())))

def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                #data가 아닌 temp임!
                if temp[nx][ny]==0:
                    temp[nx][ny]=2
                    queue.append((nx,ny))

def get_num():
    num=0
    for i in range(n):
        for j in range(m):
            #data가 아닌 temp임!
            if temp[i][j]==0:
                num+=1
    return num 

def dfs(count):
    global answer
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j]=data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j]==2:
                    bfs(i,j)
        answer=max(answer,get_num()) 
        return 
    for i in range(n):
        for j in range(m):
            if data[i][j]==0:
                data[i][j]=1
                count+=1
                dfs(count)
                data[i][j]=0
                count-=1

dfs(0)
print(answer)