[백준] 14502번 연구소 파이썬 정답 풀이

https://www.acmicpc.net/problem/14502

14502번: 연구소

---

1. 접근 방식

• 최악의 경우는 62C3 이므로, 충분히 조합으로 문제를 풀 수 있다.

전체 빈 칸들 중에서 3개를 선택한 모든 경우의 수를 계산해도 되는지 먼저 파악했다. 지도의 가로, 세로 크기는 최대 8이므로, 최대 64개의 칸이 존재할 수 있고, 그 중 바이러스가 최소 2칸을 차지하므로 빈 칸의 개수는 최대 62개이다. 62개 중에서 3개를 순서 상관 없이 고르는 것이므로 위 조합이 나왔고, 대략 2^15 정도이다. 이 정도 복잡도는 충분히 계산할 수 있다고 판단했다!

물론 추가로 각 조합마다 bfs/dfs와 빈 벽 세기 등의 작업이 동반되지만, 그 정도 연산은 무리 없다.

보통 10^6 정도의 복잡도까지는 컴퓨터가 계산할 수 있다.

 

 

• 문제에 나온 대로 필요한 함수를 떠올리자.

1. 가장 먼저 빈 칸들 중에서 3개를 뽑는 조합을 구하는 함수
2. (각 조합대로 빈 칸에 벽을 세운 후) 바이러스가 퍼지는 작업을 처리하는 bfs/dfs 함수
3. (바이러스가 퍼진 상태에서) 0의 개수를 구하는 함수

대략적으론 이 3개의 함수가 핵심이다. 1번 함수에서 구한 조합들의 리스트를 반복문을 돌려, 2번과 3번 함수를 작업하면 된다. (필자는 재귀 대신 반복문으로 작업 가능한 bfs 방식을 사용했다)

각 조합의 결과, 즉 0의 개수들 중에서 가장 큰 값이 바로 정답이다.

 

 

• 2차원 리스트의 copy

1차원 리스트는 copy() 메서드를 통해 기존 리스트의 값만 동일하게 가지는 완전 다른 리스트를 생성할 수 있다.

그러나 리스트(mutable) 안에 리스트(mutable)이 있는 2차원 리스트는 안에 있는 리스트는 copy() 하더라도, 원소(리스트)는 동일한 주소를 가리킨다. 따라서 값만 동일한, 완전히 다른 리스트를 만들고 싶다면 copy()만으론 안 된다.

슬라이싱을 활용하거나 copy 모듈의 deepcopy()를 사용하는 등 방법은 다양한데, 필자는 아래 코드에 작성된 것처럼 각 배열의 행(리스트)를 복사해서 새로운 리스트에 추가하는 방법으로 deepcopy() 메서드를 직접 정의했다.

 

 

 

2. 정답 코드

from collections import deque
import sys

input = sys.stdin.readline
R = 3


def get_empty_combination(depth, index, length, sequence):  # 빈 칸들의 조합
    if depth >= R:
        empty_combinations.append(sequence.copy())
        return

    for i in range(index, length):
        sequence.append(i)
        get_empty_combination(depth + 1, i + 1, length, sequence)
        sequence.pop()


def infect_virus(graph):
    directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]
    queue = deque(virus)
    while queue:
        x, y = queue.popleft()
        for d in directions:
            dx, dy = x + d[0], y + d[1]
            if dx < 0 or dx >= N or dy < 0 or dy >= M:
                continue
            if graph[dx][dy] == 0:
                graph[dx][dy] = 2
                queue.append((dx, dy))


def deepcopy(array):  # 2차원 배열 copy
    graph = []
    for arr in array:
        graph.append(arr.copy())
    return graph


def solve(walls):
    graph = deepcopy(maps)
    for wall in walls:
        i, j = empties[wall]  # 벽 세우기
        graph[i][j] = 1
    infect_virus(graph)  # 바이러스 전파된 상태

    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                count += 1

    return count


# main
N, M = map(int, input().split())
maps = []
empties = []  # 빈 칸 위치 정보 ex) [(0, 1), (2, 3)...]
virus = []  # 바이러스 위치 정보 ex) [(0, 0), (1, 2)...]
empty_combinations = []  # nCr (n: 빈칸 개수, r: 3) 조합

for n in range(N):
    row = list(map(int, input().split()))
    maps.append(row)
    for m in range(M):
        if row[m] == 0:
            empties.append((n, m))
        elif row[m] == 2:
            virus.append((n, m))

get_empty_combination(0, 0, len(empties), [])

result = 0
for combination in empty_combinations:
    result = max(result, solve(combination))
print(result)