범위가 그리 크지 않기 때문에 내리는 비의 양을 완전탐색하고 그때마다 높이를 기준으로 dfs나 bfs를 돌리면 된다.
이 문제는 dfs로 풀어봤다.

주어진 집합에서 수 6개를 고르는 경우의 수를 완전탐색하는 문제다.
사전순 출력이기 때문에 dfs로 순차 출력하면 된다.

주어진 지도의 크기가 최대 8 * 8이므로 바이러스와 벽이 아무것도 없다고 가정하면 벽을 세울 수 있는 경우의 수는 64C3 대략, 40,000 가지이다.
그러므로 벽을 세우는 문제는 완전탐색으로 해결할 수 있다.
벽을 세우는 모든 방법의 수 마다 바이러스가 퍼지는 경우를 dfs로 탐색하고 안전영역이 가장 큰 경우의 수를 기억해 마지막에 전체 칸의 갯수 - 퍼진 바이러스의 갯수 - 처음에 있던 벽의 갯수 - 3을 출력한다.

bfs로도 풀 수 있다. 귀찮아서 안 해봤다.

n이 최대 15이기 때문에 최악의 경우에도 2^15가지의 경우의 수를 가진다.
따라서 완전탐색을 해도 문제가 없다.
하지만 동적 계획법으로도 해결할 수 있기 때문에 두가지 방법을 다뤄보겠다.