[DFS/BFS] 연구소

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간:  40 +a

1. 문제 설명

- 바이러스를 막기 위해 울타리를 세우는 경우 중 안전지대를 최대한 많이 확보하는 방법을 찾는 문제

2. 접근 방식

- DFS문제인 거 같았다. 하지만 접근 방법을 동서남북을 다 살펴보는 방법까지는 생각했는데 그 이상은 생각하지 못했다.

- 결국 해답을 봤을 때, '조합'을 이용하는 문제였다. 참조한 해답지에서는 dfs를 활용해서 조합을 구현했다.  

- dfs구조를 보게 되면 count가 3일 경우 virus검사를 진행하고, 점수를 출력한다.
- 3이 아니라면 계속해서 재귀로 들어가면서 울타리를 치고 또 거두면서 진행한다. 

3. 코드

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

# 깊이 우선 탐색을 이용해 각 바이러스가 사방으로 퍼지도록 하기 / 얼음 만들기 알고리즘
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


def dfs(count): # DFS를 이용해 울타리를 설치하면서, 매번 안전 영역의 크기 계산
    global result
    if count == 3: # 울타리 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
    for i in range(n):
        for j in range(m):
            # 들어갔다가 나오면서 울타리를 거둔다.
            if data[i][j] == 0:
                data[i][j] = 1
                count+=1
                dfs(count)
                data[i][j] = 0
                count -= 1
dfs(0)
print(result)

4. 코멘트

- 상당히 복잡하게 재귀적으로 진행되기에 내부 상황은 모르더라도 어느정도 어떻게 구현이 되겠다. 라는 생각을 가지고 문제를 풀 수밖에 없어보인다. 해당 문제는 DFS에 대한 정확한 이해가 있어야 풀 수 있는 문제라고 생각한다.