13443번 - 바둑 분류

민호화 강호는 바둑을 하고 있다. 민호는 흑색, 강호는 백색이다.

현재 바둑판 위에는 백돌이 인접해 있지 않다. 강호는 이미 항복한 상태로 바둑판 위에 돌을 더 놓을 수 없다. 민호는 바둑판 위에 돌을 더 놓을 수 있으며, 바둑판 위의 빈 칸의 개수를 최대로 하려고 한다.

민호는 바둑판 위의 빈 칸에 흑돌을 올려놓을 수 있다. 올려놓은 후에는 죽은 백돌을 바둑판 위에서 모두 제거한다. 백돌이 죽었다는 것은 그 칸과 인접한 칸 중에 빈 칸이 없다는 것을 의미한다.

바둑판의 상태가 주어졌을 때, 민호가 만들 수 있는 빈 칸 개수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 바둑판의 가로/세로 크기 N이 주어진다. (3 ≤ N ≤ 50)

둘째 줄부터 N개의 줄에는 바둑판의 상태가 주어지며, 아래 3개의 글자 중 하나이다.

• 'o': 백돌
• 'x': 흑돌
• '.': 빈 칸

백돌이 인접한 경우는 없으며, 모든 백돌은 적어도 하나의 빈 칸과 인접해 있다.

첫째 줄에 만들 수 있는 빈 칸 개수의 최댓값을 출력한다.

예제 1의 경우에 (1, 2), (2, 1), (2, 3), (3, 2)에 흑돌을 놓으면 아래와 같은 상태가 된다.

.x.
x.x
.x.

예제 2의 경우에는 아무 돌도 놓지 않는 것이 빈 칸 개수의 최댓값이다.