[파이썬] 백준 알고리즘 No.14502 연구소

파이썬 백준 14502번 연구소 문제

 

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):
    global result
    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

    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)

 

바이러스를 벽으로 어떻게 가두어야 제일 많은 안전 공간을 확보할 수 있냐의 문제이다.

주어진 벽은 총 3개, 맵의 크기는 8 * 8

총 64C3의 경우의 수를 모두 비교해 제일 많은 공간을 뽑아내면 된다.

비어있는 모든 공간에 3개의 벽을 설치하고, 그때마다의 안전 공간의 크기를 계산한 뒤 비교한다.

이렇게 연산하여 가장 많은 안전 공간을 출력해주면 된다.

BFS/DFS에 브루트포스가 함유된 알고리즘이었다.