[백준]14502번 연구소 BFS - python

문제

 

 

이 문제는 미로찾기 문제의 꽤 까다로운 응용 버전이였다.

벽을 무조건 3개 세우는데 어디다 세워야 안전영역 크기가 최대가 될지 감이 전혀 안잡혔다.

 

 

그래서 생각한 것은 범위가 그렇게 크지 않기 때문에 벽을 3개 세우는 모든 경우의 수에서의 안전 영역을 확인해주면 된다.

이때 주의 해야할 것은 2차원 배열은 단순 copy가 아닌 deepcopy라는 것을 해주어야 기존의 배열의 값에 영향을 주지 않으면서 복사를 할 수 있다.

 

 

import copy
tmp = deepcopy(graph)

 

 

안전영역의 개수를 확인하는 것은 기존에 BFS 미로찾기 방식과 동일하다.

바이러스가 퍼질 수 있는 곳을 확인해서 퍼진 후에 안전영역의 개수를 세주면 된다.

 

def bfs():
    tmp = deepcopy(graph)
    q = deque()

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

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


    while(q):
        a,b = q.popleft()
        for k in range(4):
            x = a + dx[k]
            y = b + dy[k]
            if 0<= x <n and 0<= y <m and tmp[x][y] == 0:
                tmp[x][y] = 2
                q.append((x,y))
    global answer
    cnt = 0
    for i in range(n):
        cnt += tmp[i].count(0)

    #안전영역 더 큰걸로 답 갱신
    answer = max(answer,cnt)
    return answer

 

 

 

여기서 관건은 어떻게 벽을 3개 세우는 것을 확인하는 지 이다.

 

이 부분은 makeWall이라는 함수를 통해서 재귀를 통해 확인해준 후 원상복구를 통해 가능한 모든 경우의 수를 확인해주면 된다.

 

def makeWall(cnt):

    if cnt == 3:
        bfs()
        return answer
    
    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

 

 

 

 

 

 

 

전체 코드

 

from collections import deque
from copy import deepcopy 
n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

def bfs():
    tmp = deepcopy(graph)
    q = deque()

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

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


    while(q):
        a,b = q.popleft()
        for k in range(4):
            x = a + dx[k]
            y = b + dy[k]
            if 0<= x <n and 0<= y <m and tmp[x][y] == 0:
                tmp[x][y] = 2
                q.append((x,y))
    global answer
    cnt = 0
    for i in range(n):
        cnt += tmp[i].count(0)

    #안전영역 더 큰걸로 답 갱신
    answer = max(answer,cnt)
    return answer

def makeWall(cnt):

    if cnt == 3:
        bfs()
        return answer
    
    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


answer = 0
makeWall(0)
print(answer)

 

 

 

BFS와 백트래킹을 연관해서 구현하는 것이 어려웠던 문제였다. 아직 재귀와 관련 된 부분을 생각해서 설계하는 능력이 부족한 것 같다.