백준 - 연구소 (DFS, BFS, 완전탐색) / Gold 5 / 14502번

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

14502번: 연구소

 

풀이

import sys
from itertools import combinations
from copy import deepcopy


def virus(row, col):
    if row > 0 and map_lab[row - 1][col] == 0:
        map_lab[row - 1][col] = 2
        virus(row - 1, col)
    if row < N - 1 and map_lab[row + 1][col] == 0:
        map_lab[row + 1][col] = 2
        virus(row + 1, col)
    if col > 0 and map_lab[row][col - 1] == 0:
        map_lab[row][col - 1] = 2
        virus(row, col - 1)
    if col < M - 1 and map_lab[row][col + 1] == 0:
        map_lab[row][col + 1] = 2
        virus(row, col + 1)

    return


def safe_spot():
    cnt = 0
    for i in range(N):
        for j in range(M):
            if map_lab[i][j] == 0:
                cnt += 1

    return cnt


N, M = map(int, sys.stdin.readline().split())

lab_map = []
result = []

for _ in range(N):
    lab_map.append(list(map(int, sys.stdin.readline().split())))

spot = []
for i in range(N):
    for j in range(M):
        if lab_map[i][j] == 0:
            spot.append([i, j])

cases = list(combinations(spot, 3))

for case in cases:
    map_lab = deepcopy(lab_map)

    for i in case:
        map_lab[i[0]][i[1]] = 1

    for i in range(N):
        for j in range(M):
            if map_lab[i][j] == 2:
                virus(i, j)

    result.append(safe_spot())

print(max(result))

 

정말 오랜 시간을 들여 결국 혼자 힘으로 푼 문제이다.

이 문제의 알고리즘은 다음과 같은 순서로 동작한다.

 

1.  벽 세우기.
2.  바이러스 퍼뜨리기.
3.  0의 개수 세기.

2번과 3번은 사실 구현만 하면 된다.

즉, 시간복잡도에 큰 영향을 주진 않는다.

다만 1번의 "벽을 어떤식으로 세우냐"에 대한 알고리즘은 생각해야 한다.

 

먼저 벽을 세우는 모든 경우의 수를 완전탐색 할 수 있는지 입력 크기를 통해 확인하여야 한다.

이건 항상 알고리즘 문제를 풀 때 필수적으로 해야 하는 행동이다.

지도의 최대 크기가 8X8이기에 64칸이고 바이러스가 최소라 가정, 2를 빼면 62칸이다.

모든 칸에 벽을 놓을 수 있다고 가정하고 62칸에 벽 3개를 놓는 경우의 수는 62C3이다.

다른 단계의 시간복잡도를 고려하더라도 완전탐색이 충분히 가능하다고 보았다.

 

바이러스 퍼뜨리기는 재귀함수를 이용하여 DFS로 구현하였다.

(이 과정에서 문제과 관련 없지만 기억할만한 내용은

map_lab라는 2차원 배열이 mutable 객체이기 때문에

함수 인자로 넣어주지 않아도 index를 통해 값을 변경할 수 있었다.

그러나 map_lab 변수를 재할당 할 때에는 lab_map 2차원 배열을 깊은 복사로 복사하여

객체 안에 요소들까지 완전히 새로운 주소 값을 갖도록 하였다.)