[삼성SW역량][Python/BOJ] 백준 14502 연구소(DFS+BFS)

 

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

14502번: 연구소

 

 

 

 

wall()함수와 bfs() 함수가 있다. 

 

1. wall 함수는 세운 벽의 개수를 인수로 받아 3이 되면 bfs함수를 실행시킨다. 

아니라면 연구소를 돌면서 빈칸을 만나면 벽을 세우고 wall함수를 인수 1을 증가시켜 부른다. 

 

 

2. bfs 함수는 바이러스를 퍼뜨린후 안전영역의 개수를 센다.

ans 와 비교하여 가장 큰 안전영역의 개수를 저장한다. 

 

 

 

---

 

 

 

코드 : 

 

Score와 virus를 합쳐서 bfs함수로 이름지었다. 

 

 

from collections import deque
import copy
 
           
# 동 서 북 남      
dx = [0,0,-1,1]
dy = [1,-1,0,0]



def bfs() :
    global ans 
    tmp_mp = copy.deepcopy(mp)    
    for i in range(n) :
        for j in range(m) :
        	# 바이러스라면 
            if tmp_mp[i][j]==2 :
                q.append([i,j])
    while q :
        x,y = q.popleft()
        for dir in range(4) :
            nx,ny = x + dx[dir], y + dy[dir]
            # 바이러스 퍼뜨리기 
            if 0<=nx<n and 0<=ny<m and tmp_mp[nx][ny] == 0 :
                tmp_mp[nx][ny] = 2 
                q.append([nx,ny])
    
    cnt = 0
    # 안전영역의 개수 세기 
    for i in tmp_mp :
        cnt += i.count(0)
    ans = max(ans,cnt)

def wall(x) :
	# 벽을 2개 세웠다면 
    if x == 3 :
        bfs()
        return 
    for i in range(n) :
        for j in  range(m) :
            if mp[i][j] == 0:
            	# 벽을 하나 더 만들기 
                mp[i][j] = 1
                wall(x+1)
                # DFS를 갔다가 돌아옴 
                # 만들었던 벽을 제거 
                mp[i][j] = 0 


if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for _ in range(n)]
    ans = 0
    q = deque()

    wall(0)
    print(ans)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://hae-sooo97.tistory.com/31

[백준-14502번-연구소] - 파이썬

https://tooo1.tistory.com/447

[백준(BOJ)] 14502번 : 연구소 - PYTHON[파이썬]

 

 

 

복습 : 

✅ 20220701

✅ 20220914