[BOJ] 백준 14502번 - 연구소 (Python)

문제

문제 바로가기

from collections import deque
from itertools import combinations
import copy

move_y = [0, 1, 0, -1]
move_x = [1, 0, -1, 0]

def infect(graph, virus):
    q = deque()

    for v in virus:
        q.append(v)

    while q:
        y, x = q.popleft()
        for i in range(4):
            vy = y + move_y[i]
            vx = x + move_x[i]
            if vy >= n or vx >= m or vy < 0 or vx < 0:
                continue
            elif graph[vy][vx] == 0:
                graph[vy][vx] = 2
                q.append((vy, vx))
            else:
                continue
                
def detect_zero(graph):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                cnt += 1
    return cnt

def print_graph(graph):
    for line in graph:
        print(line)

g = list()
n, m = map(int, input().split())

for _ in range(n):
    g.append(list(map(int, input().split())))

# save_g = copy.deepcopy(g)

empty = list()
virus = list()
result = list()

for i in range(n):
    for j in range(m):
        if g[i][j] == 0:
            empty.append((i, j))
        elif g[i][j] == 2:
            virus.append((i, j))

empty_list = list(combinations(empty, 3))

for empty in empty_list:
    temp = copy.deepcopy(g)
    w1, w2, w3 = empty
    y1, x1 = w1
    y2, x2 = w2
    y3, x3 = w3
    temp[y1][x1] = temp[y2][x2] = temp[y3][x3] = 1
    infect(temp, virus)
    result.append(detect_zero(temp))

print(max(result))

문제 해결

브루트-포스 알고리즘

브루트 포스 알고리즘은 완전 탐색 알고리즘의 다른 이름이다. 완전 탐색 알고리즘은 말 그대로 가능한 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족하는 결과만을 가져온다는 것이다.

• 일반적으로 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 떠올려야 한다.
• 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 가장 기본적인 도구이다.

접근

일단 N과 M이 3이상, 8이하라고 제한되어 있다는 점에서 어떻게 구워 삶아도, O(N^3)이 되어도 메모리나 시간적으로 충분하다고 판단을 할 줄 알았어야 했다. 사실 처음 문제를 딱 봤을 때 막 말도 안되고, 인공지능이 풀어야 풀 것 같은 느낌을 받았는데, 완전 탐색으로 모든 경우의 수를 다 따져버리면 예측해서 최대의 공간을 아는 것이 아니라 모든 경우를 이미 다 실행해서 결과를 모은 뒤 최대값을 알면 되기 때문에 충분히 가능한 방법이었다.

그래프를 반복해가며 조작하거나 그래프안에 무언갈 그릴 때는 늘 처음 상태로 돌려야 하는 상황이 발생하는데, 이때 사용할 방법으로 두 가지가 있었다.

1. 특정 요소들을 리스트로 저장해두고 해당하는 그래프를 다시 그리는 방법
   • 귀찮지만 메모리 면에서 원래 그래프 공간만 계속 사용하기 때문에 더 효율적이다.
2. 그래프를 복사해두었다가 copy.deepcopy(list)하는 방법
   • 이 방법은 아예 다른 객체를 만드는 거라 너무 많은 반복은 메모리가 낭비될 우려가 있을 것 같았다.

좀 더 꼼꼼히 풀어야 겠다…