백준 14502번: 연구소 - 파이썬(DFS/BFS)

2가지 알고리즘을 이용하여 풀 수 있다.

1. BFS

2. bruteforce

 

첫번째로 BFS알고리즘은 주어진 그래프에서 탐색을 하기 위한것이므로 BFS문제를 많이 풀어본 사람이라면 쉽게 풀 수 있을것이다.

 

두번째로 이 문제에서 bruteforce는 벽을 세울 때 사용한다. 문제에서 입력값의 범위가 크지 않으므로 모든 범위를 계산해서 제일 큰 값을 고르면 된다.

 

참고로 제출할 때 python3이 아닌 pypy3로 제출해야 통과된다.

python은 시간초과가 뜬다.

왜 이렇게 다른지는 나중에 ㅠㅠ

 

아이디어를 코드로 구현하는 것과

여러가지 환경설정에 대해서 알아야 할 부분도 많다 ㅠㅠ

가야할 길이 많지만 차근차근 꾸준히 걸어가자!

 

# 14502번: 연구소
from collections import deque
import copy
import sys

def bfs():
    queue =deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[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 0 <= nx < n and 0 <= ny < m:
                if tmp_graph[nx][ny] == 0:
                    tmp_graph[nx][ny] = 2
                    queue.append((nx,ny))

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

    answer = max(answer,cnt)

def makewall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph [i][j] = 1
                makewall(cnt+1)
                graph[i][j] = 0

input = sys.stdin.readline
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))
# 상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

answer = 0
makewall(0)
print(answer)