이해

• 연구소는 크기가 N x M이고, 빈 칸은 0, 벽은 1, 바이러스가 있는 곳은 2로 표현된다.
• 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있고, 연구소에 새로운 벽 3개를 세워야 한다.
• 벽 3개를 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
• 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 출력하라.

계획

• 빈 칸에 3개의 벽을 세울 수 있는 모든 조합을 고려한다.
  • 파이썬에서 제공하는 itertools module의 combinations 함수를 사용해서 모든 조합을 구해준다.
• 벽 3개를 세운 후 dfs 알고리즘을 사용하여 바이러스 전파를 진행한다.
• 바이러스 전파가 끝난 후의 연구소에서 빈 칸의 개수를 세어주어 결괏값을 업데이트시켜준다.

실행

from itertools import combinations
import copy

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


def dfs(arr, x, y, n, m):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx <= n - 1 and 0 <= ny <= m - 1 and arr[nx][ny] == 0:
            arr[nx][ny] = 2
            dfs(arr, nx, ny, n, m)


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

result = 0

for comb in combinations(empty, 3):

    for x, y in comb:
        board[x][y] = 1

    temp = copy.deepcopy(board)
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                dfs(temp, i, j, n, m)


    result = max(result, sum(arr.count(0) for arr in temp))

    for x, y in comb:
        board[x][y] = 0

print(result)

개선

• dfs 알고리즘을 사용하여 바이러스 전파를 진행할 때 각 칸의 방문 여부를 저장하고 있는 visited 배열을 선언하여 방문된 칸에서는 전파가 다시 진행되지 않도록 해준다.
• 시간복잡도에서는 차이가 없지만 코드를 돌려보면 훨씬 빠르게 돌아간다.

from itertools import combinations
import copy

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


def dfs(arr, visited, x, y, n, m):
    visited[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx <= n - 1 and 0 <= ny <= m - 1 and arr[nx][ny] == 0:
            arr[nx][ny] = 2
            dfs(arr, visited, nx, ny, n, m)


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

result = 0

for comb in combinations(empty, 3):

    for x, y in comb:
        board[x][y] = 1

    temp = copy.deepcopy(board)
    visited = [[False]*m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2 and not visited[i][j]: 
                dfs(temp, visited, i, j, n, m)


    result = max(result, sum(arr.count(0) for arr in temp))

    for x, y in comb:
        board[x][y] = 0

print(result)

• dfs 알고리즘을 사용하여 벽을 3개 세우는 모든 조합을 계산해준다.

from itertools import combinations
import copy

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

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


board = [list(map(int, input().split())) for _ in range(n)]

result = 0

def dfs(arr, x, y):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx <= n - 1 and 0 <= ny <= m - 1 and arr[nx][ny] == 0:
            arr[nx][ny] = 2
            dfs(arr, nx, ny)


def dfs_comb(count):
    global result
    
    if count == 3:
        temp = copy.deepcopy(board)
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    dfs(temp, i, j)
        result = max(result, sum(arr.count(0) for arr in temp))
    else:
        for i in range(n):
            for j in range(m):
                if board[i][j] == 0:
                    board[i][j] = 1
                    dfs_comb(count + 1)
                    board[i][j] = 0


dfs_comb(0)

print(result)

회고

• 처음에 dfs 알고리즘을 사용하여 모든 조합을 계산하려고 했는데 풀이가 잘 떠오르지 않아서 combinations 함수를 사용하여 구현하였다. dfs 알고리즘을 잘 익혀서 조합을 계산할 때 여러 풀이가 떠오를 수 있도록 해야겠다.