[백준 14502] 연구소

문제보기

해당 문제는 브루트포스와 BFS를 조합한 문제이다.

문제를 풀기 위해, 세워야 하는 벽의 갯수는 반드시 3개여야 하며, 안전 영역 크기의 최댓값을 구해야 한다.

이를 통해서 벽을 세울때는 반드시 겹치면 안되며, 벽의 위치의 조합을 구해야 하고, 해당 조합은 안전구역에서 겹치지 않는 3개의 위치여야 한다는 것을 알 수 있다..

게다가 주어진 입력값의 범위가 크지 않은 3 <= N, M <= 8인 것으로 보아, Brute Force를 써야함을 유추할 수 있다.

바이러스가 퍼질 때에는 BFS 또는 DFS로 바이러스를 퍼뜨리면 된다. (안전 영역일때만 바이러스를 퍼뜨린다는 조건을 추가해야 한다.)

문제를 푸는 방법은 다음과 같다.

1. 모든 안전 영역에 대해서 3개의 벽을 세운다.

2. 바이러스를 퍼뜨린다.

3. 안전영역의 갯수를 구한다.

생각보다 간단한 문제이지만, 나는 바이러스를 퍼뜨릴 때 BFS를 하기 위해 인접한 행렬의 셀을 구할 때, 대각선의 셀도 구하는 실수를 했었다. (해당 문제는 상하좌우만 이동 가능함)

나머지는 코드를 보면 이해할 수 있다.

import sys
from copy import deepcopy
 
inputLine = sys.stdin.readline().split()
n, m = int(inputLine[0]), int(inputLine[1])
 
matrix = [[0 for c in range(m)] for r in range(n)]
safeSectorList = list()
virusList = list()
for r in range(n):
    inputLine = sys.stdin.readline().split()
    for c in range(m):
        matrix[r][c] = int(inputLine[c])
        
        if matrix[r][c] == 0:
            safeSectorList.append((r, c))
        elif matrix[r][c] == 2:
            virusList.append((r, c))
 
# brute force for all safe sectors
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
maxCount = 0
length = len(safeSectorList)
for i in range(0, length - 2):
    for j in range(i + 1, length - 1):
        for k in range(j + 1, length):
            # copy matrix
            copy = deepcopy(matrix)
            
            # build new 3 walls
            copy[safeSectorList[i][0]][safeSectorList[i][1]] = 1
            copy[safeSectorList[j][0]][safeSectorList[j][1]] = 1
            copy[safeSectorList[k][0]][safeSectorList[k][1]] = 1
            
            # spread viruses (BFS)
            for virus in virusList:
                queue = [virus]
                visited = set()
                while queue:
                    cur_r, cur_c = queue.pop()
                    # for 4 directions
                    for dr, dc in directions:
                        nextR = cur_r + dr
                        nextC = cur_c + dc
                        # is in boundary
                        if 0 <= nextR < n and 0 <= nextC < m:
                            # is available to visit
                            if copy[nextR][nextC] == 0 and (nextR, nextC) not in visited:
                                copy[nextR][nextC] = 2
                                queue.append((nextR, nextC))
                    visited.add((cur_r, cur_c))
            
            # count safe sectors
            count = 0
            for r in range(n):
                for c in range(m):
                    if copy[r][c] == 0:
                        count += 1
            if maxCount < count:
                maxCount = count
print(maxCount)