BOJ 14502 - 연구소

문제

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

 

 

풀이

그래프의 크기가 작으므로 벽의 위치를 완전 탐색으로 지정할 수 있다

백트래킹을 이용해 벽의 위치 3개를 지정하고 BFS 탐색으로 바이러스가 퍼진 후의 빈 칸의 수를 구한다

 

모든 빈 칸에서 3개의 빈칸을 구하는 시간 복잡도는 다음과 같다

- n * m 중에서 1칸을 고른다

- (n * m-1) 칸 중에서 1칸을 고른다

- (n * m - 2) 칸 주엥서 1칸을 고른다

따라서 64 * 63 * 62다

 

바이러스가 BFS를 사용하는 시간복잡도는 O(n * m)이다

따라서 총 연산횟수는 64 * 63 * 62 * 64 = 15,998,976이므로 주어진 시간 내에 풀 수 있다

 

 

코드

pypy3

from collections import deque
 
 
def bfs():
    global answer
    bfs_visited = [[0 for _ in range(m)] for _ in range(n)]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    q = deque()
 
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 2:
                q.append([i, j])
                bfs_visited[i][j] = 1
 
    while q:
        r, c = q.popleft()
        for d in range(4):
            next_r = r + dy[d]
            next_c = c + dx[d]
            if (
                0 <= next_r < n
                and 0 <= next_c < m
                and lab[next_r][next_c] == 0
                and bfs_visited[next_r][next_c] == 0
            ):
                q.append([next_r, next_c])
                bfs_visited[next_r][next_c] = 1
 
    cnt = 0
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0 and bfs_visited[i][j] == 0:
                cnt += 1
 
    answer = max(answer, cnt)
 
 
def backtracking(wall_count):
    if wall_count == 3:
        bfs()
        return
 
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 0 and backtracking_visited[i][j] == 0:
                backtracking_visited[i][j] = 1
                lab[i][j] = 1
                backtracking(wall_count + 1)
                backtracking_visited[i][j] = 0
                lab[i][j] = 0
 
 
answer = 0
n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]
backtracking_visited = [[0 for _ in range(m)] for _ in range(n)]
 
backtracking(0)
print(answer)