[백준] [DFS / BFS] [백트래킹] 14502. 연구소

14502. 연구소

14502번: 연구소

 

 

• 내 풀이
  • 2차원 배열은 무조건 deepcopy 사용할 것
  • 백트래킹으로 dfs에서 벽 하나씩 다 세워보기
  • 복사한 리스트로 bfs에서 바이러스 퍼뜨리고 개수 세기

from collections import deque
import copy

r,c=map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(r)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
queue=deque()
answer=0


def dfs(cnt):
    if cnt==3:
        tmp=copy.deepcopy(graph)
        for p in range(r):
            for q in range(c):
                if tmp[p][q]==2:
                    queue.append((p,q))
        bfs(tmp)
        return

    for i in range(r):
        for j in range(c):
            if graph[i][j]==0:
                graph[i][j]=1
                dfs(cnt+1)
                graph[i][j]=0



def bfs(tmp):
    global answer
    visited = [[False for _ in range(c)] for _ in range(r)]

    while queue:
        x,y=queue.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if nx<0 or nx>=r or ny<0 or ny>=c: continue
            if visited[nx][ny]==True: continue
            if tmp[nx][ny]==1: continue

            visited[nx][ny]=True
            if tmp[nx][ny]==0:
                tmp[nx][ny]=2
                queue.append((nx,ny))

    answer=max(answer, count(tmp))


def count(tmp):
    result=0
    for i in range(r):
        for j in range(c):
            if tmp[i][j]==0:
                result+=1

    return result

vst=[[False for _ in range(c)] for _ in range(r)]

dfs(0)

print(answer)