연구소

 

 

문제

0 - 빈칸, 1 - 벽, 2 - 바이러스일 때,

바이러스는 상하좌우로 0이 있으면 그 길을 통해 퍼진다.

이 때 벽을 3개 세워 바이러스를 막을 때,

바이러스가 아닌 부분의 최대 개수 (안전영역)

 

 

유형 분석

- 그래프와 연결된 모든 노드를 구해서 바이러스가 퍼지는 유형

-> DFS

 

벽을 세우는 경우의 수 : combinations

바이러스 처리 : DFS or BFS

 

 

 

코드

# 연구소

from itertools import combinations
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def virus(x, y, test):
    for k in range(4):
        now_x = x + dx[k]
        now_y = y + dy[k]
        if now_x < 0 or now_x >= n or now_y < 0 or now_y >= m:
            continue
        if test[now_x][now_y] == 0:
            test[now_x][now_y] = 3
            virus(now_x, now_y, test)

def solution(array, n, m):

    # 벽을 놓기 위한 0의 위치 구하기
    walls = []
    for i in range(n):
        for j in range(m):
            if array[i][j] == 0:
                walls.append([i, j])
    
    # 빈곳에 벽을 3개 놓는 모든 조합
    com_walls = list(combinations(walls, 3))

    # 경우의 수 처리
    result = []
    for com_wall in com_walls:

        # 테스트 맵 항상 초기화
        test = [[] for _ in range(n)]
        for i in range(n):
            for j in range(m):
                test[i].append(array[i][j])
        for wall in com_wall:
            test[wall[0]][wall[1]] = 1
        

        # 감염 처리
        for i in range(n):
            for j in range(m):
                if array[i][j] == 2:
                    virus(i, j, test)


        # 감염안된 부분 계산
        count = 0
        for i in range(n):
            for j in range(m):
                if test[i][j] == 0:
                    count += 1
        result.append(count)

    
    print(max(result))
        




array = [
    [2, 0, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 1, 2, 0],
    [0, 1, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0]
]
array = [
    [0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 2],
    [1, 1, 1, 0, 0, 2],
    [0, 0, 0, 0, 0, 2]
]
array = [
    [2, 0, 0, 0, 0, 0, 0, 2],
    [2, 0, 0, 0, 0, 0, 0, 2],
    [2, 0, 0, 0, 0, 0, 0, 2],
    [2, 0, 0, 0, 0, 0, 0, 2],
    [2, 0, 0, 0, 0, 0, 0, 2],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0]
]
n = 8
m = 8
import time
start = time.time()
solution(array, n, m)
end = time.time()
print(end-start)