백준 14502번: 연구소

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 탐색 중 너비 우선 탐색 (BFS)
• 브루트포스 알고리즘 (Brute-force search)
  
  

✔ 정답 코드

import sys
from collections import deque
from itertools import combinations
import copy

N, M = map(int, sys.stdin.readline().split())
Map = []
for _ in range(N):
    Map.append(list(map(int, sys.stdin.readline().split())))


def findVirusPoint(Map):
    virusPoints = []
    for i in range(N):
        for j in range(M):
            if Map[i][j] == 2:
                virusPoints.append([i, j])
    return virusPoints


def findZeroPoint(Map):
    zeroPoints = []
    for i in range(N):
        for j in range(M):
            if Map[i][j] == 0:
                zeroPoints.append([i, j])
    return zeroPoints


def virusSpread(Map, virusPoints):  # BFS를 통해 바이러스가 퍼져나가는 상황을 시뮬레이션
    queue = deque(virusPoints)
    while queue:
        curY, curX = queue.popleft()
        if curX > 0 and not Map[curY][curX-1]:
            Map[curY][curX-1] = 2
            queue.append([curY, curX-1])
        if curX < M-1 and not Map[curY][curX+1]:
            Map[curY][curX+1] = 2
            queue.append([curY, curX+1])
        if curY > 0 and not Map[curY-1][curX]:
            Map[curY-1][curX] = 2
            queue.append([curY-1, curX])
        if curY < N-1 and not Map[curY+1][curX]:
            Map[curY+1][curX] = 2
            queue.append([curY+1, curX])


def buildWall(Map, zeroPoints):
    testCases = list(combinations(zeroPoints, 3))
    maximum = 0
    for case in testCases:  # 가능한 모든 경우를 다 탐색하는 브루트포스 알고리즘
        testMap = copy.deepcopy(Map)
        testMap[case[0][0]][case[0][1]] = 1
        testMap[case[1][0]][case[1][1]] = 1
        testMap[case[2][0]][case[2][1]] = 1
        virusSpread(testMap, findVirusPoint(testMap))
        curSafePoints = findZeroPoint(testMap)
        if len(curSafePoints) > maximum:
            maximum = len(curSafePoints)
    return maximum


print(buildWall(Map, findZeroPoint(Map)))

코드의 길이가 길기는 하지만, 브루트포스 알고리즘이다보니 아이디어 자체는 크게 어렵지 않았다. 다만 사용한 모듈이 조금 새롭기에 포스팅하게 되었다.

• 문제를 푸는 전체적인 흐름

1. 연구소의 데이터가 들어있는 2차원 배열을 탐색하여 0이 들어가있는 지점들을 찾은 후, 이 중에서 임의로 3곳을 선택해 벽을 세운다.
2. 세워진 벽을 포함하여 바이러스가 퍼져나가는 상황을 시뮬레이션 하고, 안전 영역의 개수를 헤아린다.
3. 위의 과정을 모든 경우 (임의로 3곳을 선택해서 벽을 세우는 모든 경우) 에 대해서 반복적으로 실행하며, 안전 영역의 최댓값을 구한다.

• itertools 라이브러리의 활용
  초기에 데이터가 0인 지점들 중에서 순서 없이 3개를 선택하는 모든 경우의 수를 고려해야한다. 따라서 itertools 라이브러리의 combinations 메서드를 활용하여 모든 경우의 수를 배열에 담았다. (이때, 반드시 list로 감싸줘야 한다. 그냥 쓰면 유사 배열이라서 처리에 어려움이 있다.)
  배열 안에는 각 케이스가 tuple의 형태로 담겨 있으며, 각 tuple에는 좌표를 나타내는 배열이 3개씩 들어있게 된다.

from itertools import combinations
testCases = list(combinations(zeroPoints, 3))

• copy 라이브러리 활용
  우리는 매 케이스마다 배열에 직접 변화를 가하며 시뮬레이션을 할 것이기 때문에, 원본 배열로부터 복사한 뒤 시뮬레이션을 돌릴 필요가 있다.
  하지만, 파이썬에서 배열은 mutable 객체이므로, 단순히 대입 연산자를 활용해서는 우리가 원하는 (원본에 변화를 미치지 않는) 복사를 할 수 없다.
  따라서 copy 라이브러리의 deepcopy 메서드를 활용해, 내부의 객체들까지 새롭게 복사해버린 testMap을 만들고, 이를 시뮬레이션에 사용하였다.

import copy
testMap = copy.deepcopy(Map)