[BOJ] Q14502 연구소

[BOJ] Q14502 연구소

Question

Language: Python

Difficulty: Gold 5

해당 문제는 임의 벽을 3개 세운 후 바이러스가 퍼진 후, 바이러스가 침투하지 못한 영역의 크기를 구하는 문제이다.

임의의 벽을 3개 세운다 –> recursion, combination를 활용할 수 있다.

바이러스가 퍼진다 –> dfs/bfs를 수행한다.

combination으로 수행하게 되면 모든 좌표에 대해서 수행하게 되면 경우의 수가 너무 많이 나오므로 recursion(BackTracking) 방식으로 수행한다. 아래와 같이 벽을 임의로 세워보면서 전체 벽의 개수가 3개가 되면 bfs를 돌려 안전영역의 크기를 구한다.

def wall(cnt):
    if cnt==3:
        bfs()
        return
    for i in range(n):
        for j in range(n):
            if graph[i][j]==0:
                graph[i][j]=1
                wall(cnt+1)
                graph[i][j]=0

Solution

from collections import deque
data = []
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

max_result = 0

def get_score(copy):
    count=0
    for i in range(n):
        for j in range(m):
            if copy[i][j]==0:
                count+=1
    return count         
    
def bfs():
    global max_result
    copy = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            copy[i][j] = data[i][j]

    queue = deque()
    for i in range(n):
        for j in range(m):
            if copy[i][j] == 2:
                queue.append((i, j))
    while queue:
        y,x = queue.popleft()
        for i in range(4):
            new_y = y + dy[i]
            new_x = x + dx[i]

            if 0 <= new_y and new_y<n and 0<=new_x and new_x < m:
                if copy[new_y][new_x] == 0:
                    copy[new_y][new_x] = 2
                    queue.append((new_y,new_x))
    max_result = max(max_result, get_score(copy))
    
def wall(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                wall(cnt + 1)
                data[i][j] = 0
                
n, m = map(int, input().split())
for i in range(n):
    data.append(list(map(int, input().split())))
wall(0)
print(max_result)