백준 14502 연구소

문제는 쉽게 이해가 갔지만, 구현하는데 있어서 조금 어려웠던 문제이다.

1. 문제 해석

벽을 3개 놓는 경우는 해당 인덱스가 0일 때를 기준으로 모든 경우를 탐색해야 하기에, 백트래킹을 통해 놓을 수 있다.

또한, BFS로 놓은 벽을 기준으로 바이러스를 퍼뜨리는 과정을 찾았을 때 0의 개수를 찾으면 되는 문제이다.

2. 코드 작성

나는 visit 배열을 통해 방문을 체크하려 했으나, 시간초과에 막혔다. 하지만, visit 배열을 쓰지 않더라도 어차피 바이러스가 퍼진 곳의 인덱스는 2로 변해야 했기에 방문 체크가 가능했다.

또한, 백트래킹의 과정이 매우 단순하다. 선택한 벽의 개수만을 매개변수로 넘겨주면 되기에 cnt만 사용된다는 점이다..

마지막으로, que에 모든 바이러스 좌표를 담는다. 처음 생각의 경우 해당 인덱스가 바이러스 좌표일 경우 BFS를 하도록 설계하였지만 굳이 이럴 필요는 없었다.

from collections import deque
import copy
import sys

input = sys.stdin.readline
n, m = map(int,input().split())
lis = [list(map(int,input().split())) for _ in range(n)]
ans = 0

mx = [1,-1,0,0]
my = [0,0,-1,1]

def bfs():
    que = deque()
    arr = copy.deepcopy(lis)
    global ans
    wall, virus = 0, 0

    # 인덱스가 2인 애들을 먼저 큐에 넣고 하나씩 빼면서 돌림
    # visit를 안쓰는 이유는 바이러스 체크 시 2를 넣기에 따로 만들필요 X
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 2:
                que.append([i,j])
            elif arr[i][j] == 1:
                wall += 1

    while que:
        tx, ty = que.popleft()
        virus += 1

        for i in range(4):
            dx = mx[i] + tx
            dy = my[i] + ty

            if 0 <= dx < n and 0 <= dy < m:
                if arr[dx][dy] == 0:
                    arr[dx][dy] = 2
                    que.append([dx, dy])

    ans = max(ans, m*n - virus - wall)

    return

def recursive(cnt):
    global ans
    if cnt == 3:
        bfs()
        return

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


recursive(0)
print(ans)