[Baekjoon] 14502번 : 연구소 (Python, 구현, BFS)

[Baekjoon] 14502번 : 연구소 (Python, 구현, BFS)

 

목차

 

 

 

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

14502번: 연구소

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 33468KB / 시간 7096ms / 코드 길이 1162B

 

해당 문제는 3개의 벽을 세워 바이러스를 막는 것이 목적입니다.

그리고 벽을 잘 세워야 최대한의 빈 칸 0을 많이 만드는 것이 추가적으로 고려해야 하는 부분입니다.

 

어떻게 고민하다가 그냥 모든 것을 다 계산해버리자는 생각(brute force)을 해버리게 됩니다.

 

zero 위치를 모두 계산하여 list에 저장해놓고 3개씩 뽑는 조합을 만들었습니다.

그리고 해당 조합 list를 기반으로 벽을 세우고 바이러스를 만났을 때 전파된 이후의 0의 개수를 세도록 하였습니다.

 

저장해놓은 살아남은 빈 공간의 최대값을 출력하는 것으로 본 문제를 해결하였습니다.

 

시간이 오래걸려 안 될줄 알았는데 되네요.

 

from collections import deque
from itertools import combinations
import copy
import sys
input = sys.stdin.readline

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

def bfs(i, j):
    q = deque()
    q.append((i, j))

    while q:
        x, y = q.popleft()
        table[x][y] = 2

        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0<=nx<n and 0<=ny<m:
                if table[nx][ny] == 0:
                    table[nx][ny] = 2
                    q.append((nx,ny))

n, m = map(int, input().split())
l = []
for i in range(n):
    l.append(list(map(int, input().split())))

zero_loc = []
for i in range(n):
    for j in range(m):
        if l[i][j] == 0:
            zero_loc.append((i,j))

three_loc = list(combinations(zero_loc, 3))

res = []
for tl in three_loc:
    table = copy.deepcopy(l)
    for idx in tl:
        table[idx[0]][idx[1]] = 1

    for i in range(n):
        for j in range(m):
            if table[i][j] == 2:
                bfs(i, j)
                
    cnt = 0
    for i in range(n):
        for j in range(m):
            if table[i][j] == 0:
                cnt += 1

    res.append(cnt)
    
print(max(res))

 

시간초과 - 방법 2 - 코드 길이 1015B

 

from collections import deque
import copy
import sys
input = sys.stdin.readline

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

def bfs():
    q = deque()

    table = copy.deepcopy(l)

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

    while q:
        x, y = q.popleft()

        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0<=nx<n and 0<=ny<m and table[nx][ny] == 0:
                table[nx][ny] = 2
                q.append((nx,ny))

    global ans
    cnt = 0

    for i in range(n):
        cnt += table[i].count(0)

    ans = max(ans, cnt)

def rec_wall(num):
    if num == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):

            if l[i][j] == 0:
                l[i][j] = 1
                rec_wall(num + 1)
                l[i][j] = 0

n, m = map(int, input().split())
l = []
for i in range(n):
    l.append(list(map(int, input().split())))

ans = 0
rec_wall(0)
print(ans)