[백준] 14502번: 연구소 - Python

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

발상은 쉽지만, 간단하다고 말하기는 어려운 문제입니다.

dfs로 풀었는데 python 시간 초과, pypy3 3043ms

그래서 조금 정리를 하려고 가져왔습니다.

---

첫 발상은 모든 빈 공간에 벽을 차례차례 세워보고

바이러스가 퍼질 공간을 dfs로 확인 한 다음

0의 개수를 count해서 max를 출력하면 되지않을까? 입니다.

그래서 밑의 코드처럼 구현했습니다.

import sys

n, m = map(int, sys.stdin.readline().split())
data = []
temp = [[0] * m for _ in range(n)]

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

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

result = 0

def move_check(x,y):
    return 0 <= x < n and 0 <= y < m


def virus(x,y):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if move_check(nx,ny):
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)


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


def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]

        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)

        result = max(result, get_score())
        return

    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1


dfs(0)
print(result)

항상 좌표 문제에는

움직일 수 있는 공간을 제한하는 move_check 함수는 필수적이라 넣었고

나머지는 그냥 생각대로 구현했습니다.

그런데 

이중 반복문이 너무 많고, 문제 조건에 의하면 

최대 계산 수가 64*63*62라 시간이 너무 많이 걸릴 것을 예상했습니다만,

최선이라고 생각해서 이런 방식으로 구현했습니다. 당연하게도 시간초과!

그래서, 뭔가 다른 방법이 있나 생각했는데

바이러스가 퍼지는 방법이 의심스럽습니다.

바이러스는 가까운 곳부터 퍼진다 => bfs로 풀어야 최적해가 나오지 않을까?

그래서 여기서부터 코드를 다시 작성했습니다.

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
maxv = 0
safe_areas = []
virus_areas = []
directions = [(0,1),(-1,0),(0,-1),(1,0)]
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            safe_areas.append((i, j))
        elif arr[i][j] == 2:
            virus_areas.append((i, j))
            
def bfs(): # 바이러스 번지는 공간 체크 
    ch = [[False]*m for _ in range(n)]
    q = deque(virus_areas)
    cnt = len(safe_areas)-3 # 벽 개수
    for i, j in virus_areas:
        ch[i][j] = True
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            xx, yy = x+dx, y+dy
            if 0 <= xx < n and 0 <= yy < m and not arr[xx][yy] and not ch[xx][yy]:
                ch[xx][yy] = True
                q.append((xx, yy))
                cnt -= 1
    return cnt

def dfs(l, start):
    global maxv
    if l == 3:
        maxv = max(maxv, bfs())
        return
    for i in range(start, len(safe_areas)):
        x, y = safe_areas[i]
        arr[x][y] = 1
        dfs(l+1, i+1)
        arr[x][y] = 0

dfs(0, 0)
print(maxv)