[백준 14502번] 연구소

import copy

def dfs(graph, x, y):
    if graph[x][y] != 2:
        return

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

        if temp_x >=0 and temp_x < n and temp_y>=0 and temp_y < m:
            if graph[temp_x][temp_y] == 0:
                graph[temp_x][temp_y] = 2
                dfs(graph,temp_x,temp_y)

def count_safe_area(graph):
    count = 0

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                count += 1

    return count

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

area = [[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

nx = [-1,1,0,0]
ny = [0,0,-1,1]

zero_area = []

max_value = 0

for i in range(n):
    area[i] = list(map(int,input().split()))

for i in range(n):
    for j in range(m):
        if area[i][j] == 0 :
            zero_area.append((i,j))

zero_area_length = len(zero_area)

for i in range(zero_area_length-2):
    for j in range(i+1,zero_area_length-1):
        for k in range(j+1,zero_area_length):
            new_area = copy.deepcopy(area)
            first = new_area[zero_area[i][0]][zero_area[i][1]]
            second = new_area[zero_area[j][0]][zero_area[j][1]]
            third = new_area[zero_area[k][0]][zero_area[k][1]]

            if first == second == third == 0:
                new_area[zero_area[i][0]][zero_area[i][1]] = 1
                new_area[zero_area[j][0]][zero_area[j][1]] = 1
                new_area[zero_area[k][0]][zero_area[k][1]] = 1
            
            for a in range(n):
                for b in range(m):
                    dfs(new_area,a,b)
            
            if count_safe_area(new_area) > max_value:
                max_value = count_safe_area(new_area)

print(max_value)

이번 문제는 0은 빈칸, 1은 벽, 2는 바이러스로 이루어진 N x M 직사각형 모양의 연구소에서 임의의 벽 3개를 세웠을 때 바이러스가 퍼진 경우 바이러스가 퍼지지 않은 안전구역(0)의 최대 값을 구하는 문제이다.

 

이 문제는 총 3가지 로직을 생각하여 풀이해야 하는데, 해당 로직은 다음과 같다.

1. 임의의 3개의 영역에 벽을 세우는 로직(모든 경우의 수를 고려해야 하므로 Brute Force 알고리즘과 조합 사용)
2. 바이러스를 퍼뜨리는 로직(DFS/BFS 알고리즘 사용)
3. 안전구역을 카운팅하는 로직

처음에 이 문제를 접했을 때, 풀이하지 못했던 이유는 1번 로직을 떠올리지 못해서이다.

 

벽을 3개를 어떻게 임의로 세울지에 대해서 떠올리지 못하였는데, 결국 3개의 벽을 세우는 모든 경우의 수를 따져보아야 하므로 Brute Force 알고리즘을 사용해야 했다.

 

또한 0으로 이루어진 영역을 중에 임의로 3개의 칸을 선택해야 하는데, 2차원 리스트에서 곧바로 조합을 사용하려니 풀이가 떠오르지 않았다. 이를 위해서 먼저 2차원 리스트를 순회하면서 0인 칸을 하나의 리스트(zero_area)에 저장해주었고 3중 반복문을 사용하여 조합을 구현하였다. (원래 조합을 구현하기 위해서는 재귀함수를 사용하는 것이 올바른 방법이지만 3개까지는 반복문을 사용하는 것이 좋다고 한다)

 

위 방식을 통해 빈칸(0)으로 이루어진 영역에 벽을 세운 뒤에는 DFS 함수(def dfs)를 사용하여 바이러스를 퍼뜨린 뒤 안전구역을 카운팅(def count_safe_area)하였다.

 

이번 문제를 풀면서 배운 점은, 구현 문제를 풀이할 때는 한번에 코드를 작성하려고 하지 않고 먼저 해당 문제에서 필요로 하는 로직들을 구분짓고, 해당 로직들을 함수를 사용하는 등 분리하여 구현하는 것이 효율적이라는 것이다.

 

앞으로 구현 문제를 풀이할 때는 먼저 필요한 로직들을 도출하고, 로직 별로 구현한 뒤에 푸는 방식으로 문제를 해결해야겠다 :)