[Algorithm] 백준 #14502 - 연구소

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

14502번: 연구소

 

📌 풀이 방법

완전탐색(Brute Force) + bfs 의 방법으로 풀어야하는 문제이다. 

브루트 포스로 벽3개의 위치로 가능한 경우의 수를 모두 구해주고, 그때마다 bfs함수를 돌려주며 안전영역(0) 갯수의 최댓값을 구한다.

 

• virus() 함수 : 바이러스를 퍼트리는 함수로, 값이 2인 지점을 만나면 큐에 넣고, 상하좌우를 살피며 0인 지역이 있으면 바이러스가 퍼진 2의 상태로 모두 바꿔준다. (result변수로 바이러스가 총 몇개의 구역에 퍼졌는지 카운트해준다)
• walls() 함수 : 세워야하는 벽의 갯수가 3개였으므로, 이중 for문을 돌면서 벽을 세우는 경우의 수를 모두 확인해주는 함수이다. 

 

import sys
from collections import deque

n, m= map(int, sys.stdin.readline().rstrip().split())
graph=[]
max_result=0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            cnt += 1  # 처음0의개수

# 바이러스 퍼지는 함수
def virus():
    visited = [[0]*m for _ in range(n)]
    result = 0
    global max_result
    q = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2:  # 바이러스이면
                visited[i][j] = 1  # 방문처리 해주고 큐에 넣어주기
                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 and visited[nx][ny] == 0:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 1
                    result += 1  # 하나 증가
                    q.append((nx, ny)) # 큐에 넣어주기]
    max_result = max(max_result, cnt-result)

def walls(cnt):
    if cnt == 3:
        virus()
        return
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1  # 벽세우기기
                walls(cnt+1)
                graph[i][j] = 0

walls(0)
print(max_result-3)

 

Python으로 돌리면 시간초과가 발생하여 PyPy3로 제출하였다.

두 개의 차이점이 무엇인지 찾아보니, Python3의 실행시 시간이 매우 오래 걸린다는 단점이 있어 이것을 개선하고자 도입한 것이 PyPy3라고 한다. 그렇다고 해서 항상 PyPy3를 사용하는 것이 효율적이지는 않다. 특정 경우에는 Python이 더 유리한 경우도 있어 적절하게 섞어 사용할 줄 알아야 한다!