백준 14502 - 연구소

14502번: 연구소 (acmicpc.net)

14502번: 연구소

 

 

문제를 살펴보면, 0인 곳으로 2(바이러스)가 퍼져나가는 시스템이다. 

그렇다면 bfs를 이용해서 경로를 찾아나가면서 0을 따라서 2(바이러스)로 변경시켜주면 좋겠다는 생각을 우선 하게 되었다.

 

일단 먼저 바이러스를 퍼트리는 bfs 함수를 구현해보자.

def bfs(temp):
    q = deque()
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                q.append((i, j))
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m:
                if temp[nx][ny] == 0:
                    temp[nx][ny] = 2
                    q.append((nx, ny))

 

bfs 함수를 일반적으로 구현하고, 0인 구역을 만나면 2를 담아주어서 바이러스를 퍼트리는 방식으로 구현할 수 있다.

 

이제 벽을 세워야하는데, 벽을 딱 3개만 세울 수 있으므로 combinations 함수를 사용해서 3개까지만 조합을 찾아준다. 이 시점에서 가장 중요한 것이 있는데 벽의 조합을 독립적으로 조절시켜주지 않으면 이전 조합을 그대로 들고 와서 graph가 변질될 수 있다. 때문에, deepcopy를 사용해서 graph를 temp라는 임시 그래프로 바꾸어주고, 3개의 조합을 찾아주는 방식을 택했다.

 

empty_spaces = [(i, j) for i in range(n) for j in range(m) if graph[i][j] == 0]

max_safe_area = 0
for walls in combinations(empty_spaces, 3):        # 새로 세울 수 있는 벽 3개 조합.
    temp = deepcopy(graph)                         # 조합을 독립적으로 조절하기 위해서 deepcopy 시켜줌.
    
    for x, y in walls:
        temp[x][y] = 1

 

이렇게 empty_space를 지정해주고 combinations 함수를 이용해서 3개의 벽 조합을 세워준다.

 

마지막으로 safe_area의 갯수를 출력하기 위해서 count_safe_area 함수를 만들어주었다.

def count_safe_area(temp):
    count = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                count += 1
    return count

 

 

<전체 코드>

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

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

def bfs(temp):
    q = deque()
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 2:
                q.append((i, j))
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m:
                if temp[nx][ny] == 0:
                    temp[nx][ny] = 2
                    q.append((nx, ny))

def count_safe_area(temp):
    count = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                count += 1
    return count

empty_spaces = [(i, j) for i in range(n) for j in range(m) if graph[i][j] == 0]

max_safe_area = 0
for walls in combinations(empty_spaces, 3):        # 새로 세울 수 있는 벽 3개 조합.
    temp = deepcopy(graph)                         # 조합을 독립적으로 조절하기 위해서 deepcopy 시켜줌.
    
    for x, y in walls:
        temp[x][y] = 1
    
    # 바이러스 퍼트리기
    bfs(temp) 
    safe_area = count_safe_area(temp)
    max_safe_area = max(max_safe_area, safe_area)

print(max_safe_area)

 

전체코드를 살펴보면, 마지막으로 bfs(temp)를 사용해서 바이러스를 퍼트리고, count_safe_area 함수를 사용해서 temp 그래프의 안전 지역 갯수를 세어준 후 안전지대의 max 값을 찾아서 출력시켜주면 끝!!!!