[백준] 14502번, 연구소 (Python)

문제

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

14502번: 연구소

 

코드

import collections, sys

n, m = map(int, input().split())
graph = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
curMax = 0

def bfs():
    global curMax
    check = [[-1] * m for _ in range(n)]
    dx, dy = [-1,1,0,0], [0,0,-1,1]
    queue = collections.deque()

    # 바이러스를 모두 돌아주기 위해서 큐에 모든 바이러스를 넣어줌
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 2:
                queue.append((x,y))
                check[x][y] = 0

    while queue: 
        x,y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            # 퍼질수 있는곳 이고(0인곳), 한번도 바이러스가 방문하지 않은 곳이면, 큐에 담는다.
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0 and check[nx][ny] == -1:
                    queue.append((nx,ny))
                    check[nx][ny] = 0
    
    # 바이러스가 다 퍼진 다음에 안전영역을 체크하여 count를 세준다.
    count = 0
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 0 and check[x][y] == -1:
                count += 1

    curMax = max(curMax, count)

# 3개의 벽을 세우는 모든 경우의 수
def recursive(index):
    # 탈출조건
    if index == 3:
        bfs()
        return
    
    for x in range(n):
        for y in range(m):
            # 일반구역이라면, 벽을 세워서 다음으로 넘긴다.
            if graph[x][y] == 0:
                graph[x][y] = 1
                recursive(index+1)
                # 재귀가 끝나면 최대로 3개의 벽을 세울수 있어서 다른곳도 세워보기 위해서 벽을 허문다. 
                graph[x][y] = 0

recursive(0)
print(curMax)

바이러스인곳 상하좌우를 모두 돌아주기 위해서 바이러스인곳을 모두 queue에 넣어준다.

 

그런다음 while문이 끝나게 되면 방문하지 않은곳은(벽제외) 모두 안전영역 이기 때문에 count를 세어주고 최댓값을 저장해준다.

 

bfs를 돌기전에 재귀함수를 이용하여 벽을 3개를 세워주고 bfs를 돌아준다.

 

재귀를 하는 이유는 벽을 3개를 세웠을때 가장 안전영역이 큰 값을 구하기 위해서 모든 경우의 수를 돌아주기 위해서 이다.

 

백준에서 python3로 제출하게되면 시간초과가 나고 pypy로 제출하면 통과된다..