개미의 개열시미 프로그래밍

[알고리즘] 백준14502 연구소 - 파이썬 본문

알고리즘/DFS, BFS, 백트래킹

[알고리즘] 백준14502 연구소 - 파이썬

YunHyeok 2021. 11. 29. 22:41
728x90
반응형

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

 

14502번: 연구소

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

www.acmicpc.net

 

 

[풀이 코드]

import copy
from sys import stdin
from collections import deque

n ,m = map(int, input().split())
graph = []
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
max_result = 0
queue = deque()
for _ in range(n):
    graph.append(list(map(int, input().split())))

def bfs(graph):
    global max_result

    while queue:
        y, x = queue.popleft()
        for l in range(4):
            ny = dy[l] + y
            nx = dx[l] + x
            if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == 0:
                queue.append((ny, nx))
                graph[ny][nx] = 2

    zero_cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                zero_cnt += 1

    max_result = max(max_result, zero_cnt)


def wallSetting(cnt):
    if cnt == 3:
        for i in range(n):
            for j in range(m):
                if graph[i][j] == 2:
                    queue.append((i, j))
        graph_copy = copy.deepcopy(graph)
        bfs(graph_copy)
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wallSetting(cnt+1)
                graph[i][j] = 0

wallSetting(0)
print(max_result)
  • 벽 세 개를 재귀를 통해 설치하는 부분은 도저히 해결하지 못해 다른 분의 블로그를 참고했다. 재귀를 하는 방법 말고 브루트 포스로 구현하는 법도 있는 것 같다.
  • 벽을 설치하는 것 외에는 별로 크게 어려움 부분은 없었다.
728x90
반응형
Comments