연구소 (bfs/dfs)

파이썬은 combinations을 활용하면 쉽게 풀수 있습니다.

저는예전 c++로 n과 m시리즈를 풀었던 걸 기억하면서 dfs 함수로 짜보고 싶어서 해당 방식으로 풀어봤습니다.

 

복습을 하고 좋았습니다. dfs로 벽을, bfs로 벽이 3개가 되었을때 바이러스를 퍼지게 한후 안전영역을 확인하면 해결 가능합니다.

 

from collections import deque

n, m = map(int, input().split())

board = [[0]*m for _ in range(n)]
mx = 0
dx = [1,-1,0,0]
dy = [0,0,-1,1]
visited= [[0]* m for _ in range(n)]

for i in range(n):
    lines = list(map(int, input().split()))
    for j in range(m):
        board[i][j]= lines[j]

def bfs():
    global board
    newBoard = [[0]*m for _ in range(n)]
    
    q = deque()
    
    for i in range(n):
        for j in range(m):
            newBoard[i][j]= board[i][j]
            if newBoard[i][j]==2:
                q.append((i,j))
    
    while q:
        front = q.popleft()
        ci = front[0]
        cj = front[1]
        
        for i in range(4):
            nextx = ci + dx[i]
            nexty = cj + dy[i]
                            
            if nextx>=0 and nextx<n and nexty>=0 and nexty<m:
                            
                if newBoard[nextx][nexty] == 0:
                    q.append((nextx,nexty))
                    newBoard[nextx][nexty]=2
    
    
    return newBoard

def calArea(board):
    r = 0 
    for i in range(n):
        for j in range(m):
            if board[i][j]==0:
                r+=1
    return r

def dfs(startix, startiy, totalNum):
    global board
    global n , m
    global visited

    if totalNum == 3:

        # for i in range(n):
        #     print(board[i])
        # print()       

        b= bfs()
        
        # for i in range(n):
        #     print(b[i])
        # print()
        r = calArea(b)
        # print(r)
        global mx
        if mx < r:
            mx = r
        return

    for i in range(startix, n):
        for j in range(0,m):
            if i == startix:
                if j <=startiy:
                    continue
            if board[i][j]==0 and visited[i][j]!=1:
                board[i][j]=1
                visited[i][j]=1
                dfs(i,j, totalNum+1)
                board[i][j]=0
                visited[i][j]=0

for i in range(0,n):
    for j in range(0,m):
        if board[i][j]==0 and visited[i][j]!=1:
            board[i][j]=1
            visited[i][j]=1
            dfs(i,j,1)
            board[i][j]=0
            


print(mx)