[백준 / BOJ] 14502 연구소

문제

출처 : www.acmicpc.net/problem/14502

14502번: 연구소

N*M그리드가 주어지고, 그리드의 상태가 주어진다.

0 : 빈칸

1 : 벽

2 : 바이러스

바이러스는 매초 상하좌우 빈칸으로 확산될수있다. 바이러스가 모두 확산된후 남아있는 빈칸의 수를 안전영역이라 한다. N*M그리드에 벽 3개를 적절히 설치했을때, 안전영역의 최대 크기를 구하는 문제다.

 

풀이

N과 M의 범위가 크지않아, 완전탐색으로 풀리는문제다.

 

시간복잡도는

1. N*M그리드 에서 3개의 빈칸을 선택하는 경우의수 : 64C3

2. 바이러스를 확산시키는 반복횟수 : 64

3. 남아있는 빈칸의 수계산 : 64

라서,

40000*O(NM^2)만큼 반복한다 (2초 아슬아슬하게 통과)

 

백 트래킹과 BFS를 이용해서 구현했는데, 

 

1. 백 트래킹을 이용해 64개의 그리드에서 중복없이 3개의 빈칸에 벽을 설치한다

2. 3개의 벽을 모두 설치했다면, BFS를 이용해 바이러스를 확산시키기 시작한다.

3. 바이러스를 더이상 확산시킬수없다면 남아있는 빈칸의 갯수를 계산한다.

모든경우를 다 봐줄때까지 위를 반복하면 끝

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14502%20%EC%97%B0%EA%B5%AC%EC%86%8C/main.cpp

devxb/JJUNalgo