[백준] 14502번 연구소 (python)

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

 

---

 

문제 풀이

너비 우선 탐색이랑 완전 탐색이 합쳐진 문제이다. 벽을 세울 수 있는 모든 경우를 만들고, 그 경우로 너비 우선 탐색을 했다. N과 M의 범위가 작기 때문에 시간초과는 안 난다.

 

제일 어려웠던 건 원본 그래프를 유지하는 부분이었다. 그래프를 바꾸면서 문제를 풀어나가야 하기 때문에 원본 그래프를 유지해야 한다. copy의 deepcopy 메서드를 써서 복사본을 만들고, 원본은 유지하면서 풀었다.

 

 

이런 문제는 구현해야 할 기능이 많아 무조건 메서드로 나눠서 푸는 게 편하다.

내가 만든 메서드는 아래와 같다.

• 벽을 세우는 메서드
• 바이러스를 퍼트리는 메서드
• 안전한 구역의 개수를 세는 메서드

안전한 영역의 최댓값 구하는 메서드도 작성할까 했으나, 이 부분은 그냥 메인에 넣어서 풀었다.

 

 

정답 코드

import sys, copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline

def spread_virus(graph, virus):
    dq = deque(virus)
    visited = [[False] * m for _ in range(n)]
    
    while dq:
        x, y = dq.popleft()

        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = True
                    graph[nx][ny] = 2
                    dq.append([nx, ny])

    return graph


def count_safezone(graph):
    count = 0

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

    return count


def build_wall(graph, locations):
    build_graph = copy.deepcopy(graph)

    for x, y in locations:
        build_graph[x][y] = 1
    
    virus = []
    for i in range(n):
        for j in range(m):
            if build_graph[i][j] == 2:
                virus.append([i, j])

    return spread_virus(build_graph, virus)


n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

walls = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            walls.append([i, j])

max_safezone = 0
for locations in combinations(walls, 3):
    result_graph = build_wall(graph, locations)
    
    safezone = count_safezone(result_graph)
    if max_safezone < safezone:
        max_safezone = safezone

print(max_safezone)