[백준] 17141번 : 연구소 2

17141번: 연구소 2

해당 문제는 완전 탐색 + 조합 + BFS 문제로 해결 하였습니다.

바이러스 후보들을 조합하여 그래프에 적용하고 퍼트립니다.

BFS를 사용한 이유는 모든 바이러스 후보들을 queue에 넣고 BFS 탐색을 시작하면 최단 거리로 탐색이 시작되기때문에 퍼지는 시간을 구할 수 있습니다.

조합은 파이썬의 내장라이브러리를 사용하지않고 DFS로 조합을 만들었습니다.

from collections import deque
from copy import deepcopy
import sys
from pprint import pprint
input = sys.stdin.readline
N, M = map(int, input().split())
moves = [(1,0), (-1,0), (0,1), (0,-1)]

EMPTY = 0
WALL = 1
VIRUS = 2

graph = []
for _ in range(N):
    graph.append(list(map(int ,input().split())))

def virus(graph):
    visited = [[False for _ in range(M)] for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if graph[i][j] == VIRUS and not visited[i][j]:
                visited[i][j] = True
                queue = deque()
                queue.append((i, j))
                while queue:
                    y, x = queue.popleft()
                    for dy, dx in moves:
                        ny, nx = y + dy, x + dx
                        if N > ny >=0 and M > nx >=0 and not visited[ny][nx] and graph[ny][nx] == EMPTY: # 빈공간을 바이러스로 만든다.
                            visited[ny][nx] = True
                            graph[ny][nx] = VIRUS
                            queue.append((ny, nx))

def safearea(graph):
    cnt = 0
    for i in range(N):
        for j in range(M):
           if graph[i][j] == EMPTY:
                cnt += 1

    return cnt

ans = 0
def dfs(idx, graph, wall):
    global ans
    if wall == 3:
        graph = deepcopy(graph)
        virus(graph)
        cnt = safearea(graph)
        #pprint(graph)
        ans = max(ans, cnt)
        return

    i = idx // M
    j = idx % N
    for y in range(N):
        for x in range(M):
            if graph[y][x] == EMPTY:
                graph[y][x] = WALL
                dfs(idx+1, graph, wall + 1)
                graph[y][x] = EMPTY

dfs(0, graph, 0)
print(ans)

해당 문제는 조합 + BFS가 핵심 입니다. 순열로 문제를 풀게 될 경우 이미 똑같은 바이러스 후보들을 방문 함으로 반드시 조합을 문제를 해결 해야 합니다.