[백준] 14502 - 연구소

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

14502번: 연구소

문제 한줄 이해

- N*M 크기의 연구소에 바이러스(2), 벽(1), 빈칸(0)이 있을때 벽 3개를 새로 세워 바이러스가 퍼져나간뒤 안전한 칸이 제일 많은 경우를 구하기!

 

생각난 풀이

1번째 방법: 먼저 백트래킹이 떠올랐다. 현재 그래프 상태에서 벽을 새로 3개를 세우는 경우를 판단하기 위해서이다. 그런 다음 백트래킹의 종료 조건절에서 BFS 탐색을 통해 바이러스가 퍼지게 한 후 안전한 칸을 카운팅했다!!!

import sys
import copy
from collections import deque
n ,m = map(int,sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

def bfs(visited):
    que = deque()
    for i in range(n):
        for j in range(m):
            if visited[i][j]==2:
                que.append((i,j))
    
    while que:
        nowx, nowy = que.popleft()
        
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            
            if nextx>=0 and nexty>=0 and nextx<n and nexty<m :
                if visited[nextx][nexty] == 0:
                    visited[nextx][nexty] = 2
                    que.append((nextx,nexty))
    
def back(start,cnt): #백트래킹
    global result
    if cnt == 3: # 벽을 3개를 다 세웠으면 바이러스 퍼지게 한후 카운팅!
        visited= copy.deepcopy(graph)
        bfs(visited)
        cnt = 0
        for i in range(n):
            for j in range(m):
                if visited[i][j] == 0:
                    cnt+=1
        if result < cnt:
            result = cnt
        return
    
    for i in range(n):
        for j in range(start,m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                back(start+1,cnt+1)
                graph[i][j] = 0
result = 0
back(0,0)
print(result)