[python] 백준14502_연구소 (DFS&BFS)

문제

 

풀이

DFS로 바이러스 퍼지게 하는 함수와 현재 맵에서 안전영역을 구하는 함수를 만들어 두고,

빈 공간에 울타리를 치는 모든 경우의 수를 DFS로 찾으면서 매번 안전영역의 크기를 검사한다.

 

 

코드

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

data = [] # 초기 맵 리스트
temp = [[0]*m for _ in range(n)]

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

# 서남동북
dx = [-1,0,1,0]
dy = [0,1,0,-1]

result = 0

# DFS로 바이러스 퍼지게 하기
def virus(x,y):
    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 :
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx,ny)

# 현재 맵에서 안전 영역의 크기 계산
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# DFS를 이용하여 울타리를 설치하면서, 매번 안전 영역의 크기 계산
def main_dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    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:
                    virus(i,j)
        
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return

    # 빈 공간에 울타리 설치 -> 울타리 설치는 빈공간이 n개 일때, nC3 개의 경우의 수를 모두 검토해야함 / 0인 좌표를 모두 구하고 모든 combination을 구해서 해도 될듯
    # i,j 순회하면서 첫 벽세우고, dfs 타고 i,j 순회하면서 2번째 벽 세우고 다시 dfs타고
    # 3번 째 벽 세우고 get_score() 안전 지역 계산하고, 재귀 풀리면서 3번째 벽 지우고 다음 위치에
    # 3번 째 벽 다시 세우고... 계속 반복하면 벽을 세울 수 있는 모든 경우의 수 다 확인
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:		# 빈 공간 일 때
                data[i][j] = 1		# 벽 세우고
                count += 1			# 벽 세울 때 마다 count +=1
                main_dfs(count)		# 다음 벽 세우기 위해 dfs
                data[i][j] = 0		# 재귀 풀리는 과정 세웠던 벽 지우고
                count -= 1			# 카운트도 복귀

main_dfs(0)

print(result)