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

<문제>

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

14502번: 연구소

<풀이>

1.울타리 설치가 가능한 모든 경우의 수를 탐색한다.(DFS알고리즘 사용)
2.각각의 경우에서 안전영역의 크기를 계산해 최댓값을 구한다.
3.안전영역의 크기를 구하는 과정

• 울타리 설치가 가능한 모든 경우의 수만큼 울타리를 설치한다.(dfs메서드)
• 울타리가 설치된 상태에서 바이러스가 퍼져나갈 수 있는 가장 넓은 영역만큼 바이러스를 퍼뜨린다.(virus함수)
• 바이러스가 퍼진 상태에서의 안전영역의 넓이를 result에 저장한다.
• 맵의 최초상태를 저장한 graph배열에서 이중반복문을 통해 위 1~3번 과정을 반복하며 result의 최댓값을 구한다.

<코드>-파이썬

 

import sys
n,m =  map(int,sys.stdin.readline().split())
graph = []
temp = [[0]*m for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

dx = [-1,0,1,0]
dy = [0,-1,0,1]

result = 0
#바이러스를 퍼지게 하는 함수
def virus(x,y):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx>=0 and ny>=0 and nx<n and ny<m:
            if temp[nx][ny]==0:
                temp[nx][ny] = 2
                virus(nx,ny)
#현재맵에서 안전영역 크기 계산 메서드
def score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score+=1
    return score


#깊이 우선 탐색(DFS를 이용해 울타리를 설치하면서 안전영역의 크기를 계산)
#count : 울타리 갯수
def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = graph[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)
        result = max(result,score())
        return

    #빈공간에 울타리 설치 
    #DFS 이용해 울타리 설치 가능한 모든경우의 수 탐색
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                count+=1
                dfs(count)
                graph[i][j] = 0
                count-=1
                #맵의 상태가  count값이 3이 된 이전과 이후가 계속해서 바뀌기 때문에 
                #모든 울타리 설치 경우의 수를 구할 수 있다.
dfs(0)
print(result)

※DFS 재귀호출부분 설명※

설명을 하기위해 임의의 다음과 같은 3*3형태의 연구소가 있다고 하자.
이 연구소에서 처음 count=3이 된 상황 이전과 이후를 나눠서 살펴보자

2	0	0
0	0	1
0	1	1

-가장처음 count=2인경우-

2	1:새로설치된 울타리	1
0	0	1
0	1	1

-가장처음 count=3인경우-

2	1	1
1	0	1
0	1	1

->count가 3이 되었으므로 위 코드의 count-=1과 graph[i][j]=0을 통해 count=2 가 되고 dfs(2)가 호출된다.
따라서 graph는 다음과 같은 형태가 된다.
dfs(2)가 호출되면서 graph[1][1] = 1이 되고 count는 다시 3이 된다.

2	1	1
0:count=3이후 상태 복구	1	1
0	1	1