백준 14502 삼성SW역량테스트 기출 (BFS Python)

백준 14502 연구소 바로가기

이 문제를 처음 봤을 때 BFS를 사용해야겠다고 바로 생각이 들었다.
총 3단계로 문제를 나눴다.
1. 벽 3개 세우기
2. 바이러스가 퍼지기
3. 0의 개수 카운트하기

우선 벽 3개를 세우는 알고리즘은 완전탐색을 선택했다.
그 이유는 최대 세로, 가로의 크기가 8이기때문에 완전탐색으로 충분히 계산 가능한 범위라고 생각했다.
그 다음 바이러스가 퍼지는 것은 BFS를 사용하여 풀어야겠다고 생각했다.
상, 하, 좌, 우를 사용해서 BFS하는 방식으로 0이면 2로 바꾸면 되겠다고 생각했다.
마지막 0의 개수 카운트는 그냥 2중 for문으로 카운트하기로 마음 먹었다.

가장 처음에 구현했을 때 바이러스가 퍼지고 나서 다시 되돌려 놓지 않아 결과가 이상하게 나왔다. 따라서 2차원 리스트를 copy하여 새로운 2차원 리스트에 바이러스를 퍼뜨리고 그때의 0의 개수를 카운트했다.

import sys
from collections import deque
import copy

def spread():
#바이러스 퍼지는 알고리즘
    pan = copy.deepcopy(pan2)
    for i in range(n):
        for j in range(m):
            if pan2[i][j]==2:
                queue.append([i,j])
    while queue:
        x, y = queue.popleft()
        for i in range(4): #상하좌우
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if pan[nx][ny]==0:
                pan[nx][ny] = 2
                queue.append([nx,ny])
#안전구역 개수 구하는 알고리즘    
    count = 0
    global answer
    for i in range(n):
        for j in range(m):
            if pan[i][j]==0:
                count += 1
    answer = max(count,answer)

def wall(wallcount):
#벽을 세우는 알고리즘
    if wallcount==3:
        spread()
        return
    for i in range(n):
        for j in range(m):
            if pan2[i][j]==0:
                pan2[i][j]=1
                wall(wallcount+1)
                pan2[i][j]=0        
n,m = map(int, sys.stdin.readline().split())
pan2 = [0 for _ in range(m)]
for i in range(n):
    pan2[i]= list(map(int,sys.stdin.readline().split()))
dx = [0,0,-1,1]
dy = [-1,1,0,0]
queue = deque()
answer = 0
wall(0)
print(answer)

그런데 이 코드를 백준에 제출했을 때 시간초과가 나왔다. 값은 분명이 제대로 나와서 어디가 문제일까를 고민해봤는데 아무래도 deepcopy가 O(NM)의 시간복잡도를 가지기 때문에 전체 실행시간이 O((NM)^2)으로 매우 컸다...

따라서 아래와 같이 deepcopy대신에 slicing을 사용해서 깊은 복사를 해주었다.

 pan = [l[:] for l in pan2]

찾아보니 리스트 슬라이싱 방식이 deepcopy방식보다 더 빠르다고 해서 바꿔주었다. 하지만 그럼에도 시간초과가 발생했다.

따라서 이중리스트를 깊은 복사하고 바이러스가 퍼지는 것을 실제로 값을 2로 변경해주는 것이 아니라 visited리스트를 만들어서 방문했다면 2로 된것이라고 가정했다.

이를 위해 visited라는 이름의 이중리스트를 만들어 바이러스가 퍼질 때 만약 감염되어야 하는 자리고, visited가 0이라면 count를 늘려주고 visited를 1로 바꾸어주었다. 이렇게 될 경우 count의 값이 새롭게 감염된 0들의 개수이기 때문에 초기의 0의 개수에서 새롭게 감염된 0의 개수를 빼고 새로운 벽의 개수 3을 빼면 감염되지 않은 칸의 개수가 나온다.
따라서 코드는 아래와 같다.

import sys
from collections import deque

def spread():
    visited = [[0]*m for i in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if pan[i][j]==2:
                queue.append((i,j))
    while queue:
        x, y = queue.popleft()
        for i in range(4): #상하좌우
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if pan[nx][ny]==0 and visited[nx][ny]==0: #감염
                visited[nx][ny] = 1
                count += 1
                queue.append((nx,ny))
    global answer

    answer = max(result-count,answer)

def wall(wallcount):
    if wallcount==3:
        spread()
        return
    for i in range(n):
        for j in range(m):
            if pan[i][j]==0:
                pan[i][j]=1
                wall(wallcount+1)
                pan[i][j]=0        
n,m = map(int, sys.stdin.readline().split())
pan = []
for i in range(n):
    pan.append(list(map(int,sys.stdin.readline().split())))
result = 0 #초기 공백
for i in range(n):
    for j in range(m):
        if pan[i][j]==0:
            result += 1
dx = [0,0,-1,1]
dy = [-1,1,0,0]
queue = deque()
answer = 0
wall(0)
print(answer-3) # 벽 3개 제거

그런데 이렇게 해도 시간초과나와서 진짜 뭐가 문젤까 하다가 다른 사람의 풀이를 참고해보자 해서 확인해봤더니 기본적인 구조가 다 비슷해서 뭐가 문제인지 확인할 수가 없었다.
결국 마지막으로 언어 pypy3로 제출했더니 내가 작성했던 모든 코드들이 맞았다.
만약 알고리즘이나 코드가 비슷한데 시간초과가 계속 나온다면 pypy3로 제출해보자.