[백준][Python] 14502번 연구소

14502번: 연구소

 

 

코드

from collections import deque
import copy

def bfs():
	queue = deque()
	c_graph = copy.deepcopy(graph)
	for i in range(n):
		for j in range(m):
			if c_graph[i][j] == 2:
				queue.append((i,j))
	while queue:
		x,y = queue.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx >= 0 and nx < n and ny >= 0 and ny < m and c_graph[nx][ny] == 0:
				c_graph[nx][ny] = 2
				queue.append((nx,ny))
	global ans
	cnt = 0
	for i in range(n):
		cnt += c_graph[i].count(0)
	ans = max(ans,cnt)
	
def wall(num):
	if num == 3:
		bfs()
		return
	for i in range(n):
		for j in range(m):
			if graph[i][j] == 0:
				graph[i][j] = 1
				wall(num+1)
				graph[i][j] = 0
                
n, m = map(int,input().split())
graph = []
ans = 0
dx = [0,0,-1,1]
dy = [-1,1,0,0]

for _ in range(n):
	graph.append(list(map(int,input().split())))
wall(0)
print(ans)

 

설명

3개의 벽을 모든 방법으로 세워보고 그때의 안전 영역을 bfs를 이용하여 찾는다.

모든 경우의 수를 고려해봐야 하므로 graph를 c_graph에 deepcopy를 해줘야 한다.