[파이썬] 백준 14502번 연구소 : DFS + 브루트 포트

연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1 ×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

소스코드

import sys; r = sys.stdin.readline
from itertools import combinations
import copy
sys.setrecursionlimit(100000)
N, M = map(int, r().split())
Vt = [[*map(int,r().split())] for _ in range(N)]
ck = [[0]*M for _ in range(N)]

# DFS 바이러스가 퍼지는 것을 구현
def dfs(V, ck, x, y):
    if ck[x][y] == 0:
        ck[x][y] = 1
        if V[x][y] == 0:
            V[x][y] = 2
        # dx, dy 하는 것 보다 if로 나누면 조금 더 수행시간이 빠릅니다.
        if x+1 < N and ck[x+1][y] == 0 and V[x+1][y] != 1:
            dfs(V, ck, x+1, y)
        if x-1 >= 0 and ck[x-1][y] == 0 and V[x-1][y] != 1:
            dfs(V, ck, x-1, y)
        if y-1 >= 0 and ck[x][y-1] == 0 and V[x][y-1] != 1:
            dfs(V, ck, x, y-1)
        if y+1 < M and ck[x][y+1] == 0 and V[x][y+1] != 1:
            dfs(V, ck, x, y+1)
    return V

# 안전지대와 바이러스의 위치를 파악합니다.
zeros = []
virus = []
for i in range(N):
    for j in range(M):
        if Vt[i][j] == 0:
            zeros.append((i,j))
        if Vt[i][j] == 2:
            virus.append((i,j))

# 벽을 세우는 부분
def blocking(Vx, ck, zeros):
    # comination 조합에 따라 벽을 세움
    for i, j in coms:
        Vx[i][j] = 1
    # 바이러스가 퍼짐
    for i, j in virus:
        Vx = dfs(Vx, ck, i, j)
    # 안전지대의 수 세기
    cnt = 0
    for i in range(N):
        for j in range(M):
            if Vx[i][j] == 0 : cnt+=1
    return cnt

max_zero = 0
# 순열조합을 활용하여 벽을 막을 수 있는 경우를 모두 고려
# 해당 부분이 비효율적인 경향이 있음
for coms in combinations(zeros, 3):
    # 값이 변하면 안되므로 deepcopy()를 활용
    # copy 모듈을 사용할 수 없다면 
    # [v for v in Vt]와 같은 방식을 활용할 수 있음
    V_in = copy.deepcopy(Vt)
    cks = copy.deepcopy(ck)
    x = blocking(V_in, cks, coms)
    max_zero = max(max_zero, x)
print(max_zero)

• 결과
  • 메모리 : 29284 KB
  • 시간 : 5116 ms
• 한마디
  • 문제가 생각보다 까다롭고 어렵게 느껴졌습니다. 정답 비율이 54.86%로 상당히 높음에도 불구하고 쉽지는 않게 느껴졌습니다. 문제를 접근하는 데 있어서 좀 더 좋은 풀이가 있을 것으로 생각되지만 제한시간을 염두하고 문제를 풀었더니 훨씬 어려웠던 것 같습니다.
• 문제 개요
  • 문제를 풀어가는 부분을 나눠서 생각해보겠습니다.
  • 전체적인 문제는 바이러스가 퍼져나가는 것을 최소한으로 막는 방법을 찾는 것입니다.
  • 방어할 수 있는 벽인 '1' 은 3개만 세울 수 있습니다.
• 문제 풀이 접근
  • 쉽게 푸는 방법이 생각나지 않아서 전체적으로 구현을 해야겠다고 생각했습니다.
  • 무엇을 구현해야하는지 생각해보겠습니다.
  • 먼저, 바이러스가 퍼지는 것
    • 바이러스가 퍼지는 것을 DFS방식으로 해결하면 될 것이라고 연결할 수 있었습니다.
  • 다음, 바이러스가 다 퍼진 후, 안전지대의 개수를 세는 것
  • 마지막으로 벽을 세우는 것
    • 이 부분을 어떻게 구현해야할 지 가장 어려웠습니다.
  • 시간적 측명
    • 벽을 세우는 부분에서 가장 문제가 있었습니다. 어떤 기준으로 벽을 세울 것인가. 쉽게 생각나지 않았습니다.
    • 전체 맵의 크기가 3 <= N, M <= 8이기 때문에 전체적으로 크지 않습니다. 또한, 시간제한도 2초 정도로 상당히 여유로운 편이라고 생각할 수 있었습니다.
    • 더 효율적인 방법으로 벽을 세우기 위한 탐색 방법이 있을 것이지만, 저는 브루드 포스 방식으로 문제를 풀기로 결정하였습니다. 전체 벽을 세울 수 있는 경우에 따라, 벽을 세우고 남은 안전지대의 수를 세어주었습니다.
• 유사한 문제 : DFS와 BFS 관련 문제
  • [파이썬/알고리즘] - [파이썬] 백준 1260번 DFS와 BFS
  • [파이썬/알고리즘] - [파이썬] 백준 2606번 바이러스 - BFS방식과 DFS 방식 비교
  • [파이썬/알고리즘] - [파이썬] 백준 2667번 단지 번호 붙이기 - DFS 방식 문제 풀이
  • [파이썬/알고리즘] - [파이썬] 백준 2178번 미로 탐색 - BFS 최단 경로 탐색

• 문제 출처

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