[BOJ] [Python] 14502번 : 연구소

문제를 정리해보자.

 

• 연구소 : N x M
  • 빈칸 : 0 ( 3개 이상 )
  • 벽 : 1
  • 바이러스 : 2 ( 2개 이상, 10개 이하 )
• 세울 수 있는 벽의 수 : 3개 (꼭 3개를 세워야 한다.)

벽을 3개 세운 뒤, 안전 영역의 크기의 최댓값을 구하는 문제이다.

 

 

 

바이러스는 bfs로 퍼트려주면 된다.

그 전에, 벽은 어떻게 세워야 할까?

 

벽을 세울 수 있는 모든 경우의 수를 탐색하면 된다.

 

먼저 bfs를 제외한 make_wall 코드를 보자.

 

재귀 함수를 이용해서 모든 경우의 수를 볼 것이다.

벽의 개수는 count 개수이고, 3개가 될 때까지 만들어준다.

 

 

import sys
from collections import deque

input = sys.stdin.readline

s = []

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

m_result = 0



def make_wall(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                s[i][j] = 1
                
                make_wall(cnt + 1)
                
                s[i][j] = 0


n, m = map(int, input().split())

for i in range(n):
    s.append(list(map(int, input().split())))

make_wall(0)

print(m_result)

 

 

 

다음은 전체 코드이다. bfs 함수를 보자.

 

tmp는 grahp의 본사본이고, 이것을 이용해서 바이러스가 퍼지는 위치를 따질 것이다.

( 벽의 위치에 따라 바이러스가 퍼지는 위치가 다르므로, grahp를 건들면 안 된다. )

 

target이하는 deque에 바이러스의 위치를 넣어준다.

바이러스를 하나씩 빼면서 bfs를 돌린다. 

dx와 dy를 이용해서 상하좌우의 위치를 구하고

빈칸이면서, 각각 n과 m를 넘지 않는 조건을 만족하면, 위치를 target 리스트에 넣어준다.

 

bfs가 끝나고 났을 때, 위치에 1이 있는 자리가 안전 영역이다.

 

 이렇게 벽의 위치에 따른 청정구역의 위치를 구하고, 그 중 최대값을 구하면 된다.

 

import sys
from collections import deque

input = sys.stdin.readline

s = []

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

m_result = 0


def bfs():
    global m_result

    tmp = [[0] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            tmp[i][j] = s[i][j]

    result = 0

    target = deque([])

    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 2:
                target.append([i, j])

    while target:
        var = target.popleft()
        a = var[0]
        b = var[1]

        for i in range(4):

            ax = a + dx[i]
            ay = b + dy[i]

            if 0 <= ax < n and 0 <= ay < m:
                if tmp[ax][ay] == 0:
                    tmp[ax][ay] = 2

                    target.append([ax, ay])
    for li in tmp:
        for num in li:
            if num == 0:
                result += 1
                
    m_result = max(m_result, result)


def make_wall(cnt):
    if cnt == 3:
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                s[i][j] = 1
                
                make_wall(cnt + 1)
                
                s[i][j] = 0


n, m = map(int, input().split())

for i in range(n):
    s.append(list(map(int, input().split())))

make_wall(0)

print(m_result)

 

 

바이러스가 퍼지는 것은 BFS로 해결하면 된다고 생각했다.

하지만 벽을 어떻게 세워야 할지가 고민이었다.

 

항상 알고리즘 문제를 풀면서 느끼는 것이지만, 너무 깊게 생각할 필요가 없다는 것이다. 

문제를 오래 붙잡고 있을수록, 숲을 보지 않고 나무만 보려는 경향이 생기는 것 같다.

사람과 달리 컴퓨터는 모든 경우의 수를 탐색할 수 있다.

이 점을 잊지 말자.