코드

import copy
from collections import deque

n, m = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

# BFS 구현
def bfs(answer):
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    q = deque()
    
    # 벽을 설치한 후의 상태를 담을 그래프
    # 원래의 그래프를 deepcopy로 깊은 복사를 해줌
    after = copy.deepcopy(graph)   
    
    # 바이러스가 존재(2)하는 곳의 좌표만
    # 큐에 담음
    for i in range(n):
        for j in range(m):
            if after[i][j] == 2:
                q.append((i, j))
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            # 0인 경우 바이러스 감염 가능
            if after[nx][ny] == 0:
                after[nx][ny] = 2
                q.append((nx, ny))
                
    # 벽을 설치한 경우마다 남아있는 0의 개수를 담을 변수
    cnt = 0
    
    # q가 빌 때까지 반복을 수행한 후
    # 그래프에 남아있는 0의 개수를 cnt에 누적하여 담음
    for i in range(n):
        cnt += after[i].count(0)
        
    # 가장 0이 많은 경우가 정답
    # answer와 cnt 중 더 큰 값으로 answer를 선택
    answer = max(answer, cnt)
    return answer
    
    
# bfs로 반환된 answer들의 결과를 담을 리스트    
result = []

# 로직 구현
def solution(wall_cnt):
    
    # 모든 경우를 다 비교한 후 최종 0의 개수가 담길 변수
    answer = 0
    
    # 벽을 3개 설치했으니 bfs 시작
    # bfs의 결과를 result에 담음
    if wall_cnt == 3:
        result.append(bfs(answer))
        return 
    
    # 벽 설치와 삭제를 반복함
    # 백트래킹을 구현하여
    # 바이러스가 퍼질 수 있는 모든 좌표에 대하여
    # 로직을 수행
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1 # 벽 설치
                solution(wall_cnt+1)
                graph[i][j] = 0
                
# 설치한 벽의 개수를 담을 변수             
wall_cnt = 0

# 로직 수행
solution(wall_cnt)           

# result중 가장 큰 값이 정답
print(max(result))

문제 해설

BFS의 응용 문제.

일반적인 BFS에 벽을 추가한다는 개념을 도입하여, 퍼지는 바이러스를 가장 효과적이게 막을 수 있는 경우를 찾는 문제이다.

처음 문제에 접근할 때 단순히 BFS라고 쉽다고 생각하여 시도하였다가 난관에 봉착하였다.

벽을 설치하는 것을 코드로 어떻게 표현할까??

위의 방법을 생각하는 것이 매우 어려웠다. 시도를 해봤을 때 결국 백트래킹을 활용하면 좋겠다는 것을 깨달았으나, 이것을 코드로 구현하는 것은 또 별개의 문제.

결국 구글링을 통하여 방법을 체득하였다.

내가 어렵게 생각한 부분은 아래와 같다.

  1. 벽을 설치하는 모든 경우에 대하여 주어진 그래프를 매번 카피해야 함
  2. BFS와 백트래킹을 어떤 방법으로 엮으면 좋을지 모름

1번의 경우, 벽을 3개 설치한 후, 완전히 기존의 그래프와 똑같은 상태로 다시 다른 3개를 설치하는 과정을 반복해야 한다는 것을 간과하였다.

2번의 경우, 백트래킹으로 벽을 3개까지 설치하고 그 후에 BFS를 수행하면 된다는 것을 파악하였다.

위 두 난관을 구글링을 통하여 학습하였고 결국 정답으로 인정받을 수 있었다.

또한, Python3이 아닌 Pypy3으로 정답을 인정받았는데, 후에 시간 복잡도 적으로 더 좋은 코드 방법이 있는지 참고하여 공부를 따로 진행해봐야겠다.

댓글남기기

참고