테두리

시간 제한4초메모리 제한1024 MB

요약

흑백 격자가 주어질 때, 모든 영역이 테두리를 갖도록 테두리를 그릴 같은 색 연결 영역의 최소 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, DFS, 그리디, 트리
정답자: 아직 제출이 없습니다

문제

각 픽셀의 값이 0 또는 1인 흑백 이미지가 있다. 이미지의 영역이란 같은 값을 가지면서 서로 연결된 픽셀의 모임이다. 구체적으로, 한 영역의 임의의 두 픽셀 사이에는 상하좌우로만 이동하고 같은 값을 가진 픽셀만 지나는 경로가 존재한다.

이미지의 모든 영역 둘레에 테두리가 완전히 둘러져 있기를 원한다. 어떤 영역을 골라 그 영역 둘레에 테두리를 그릴 수 있는데, 그렇게 하면 영역 내부의 "구멍"(영역 안에 완전히 포함된 영역)까지 포함하여 영역 전체 둘레에 테두리가 그려진다. 두 영역이 인접해 있으면 둘 중 하나의 둘레에 테두리를 그리거나, 둘 다 그려서 두 영역 사이의 테두리를 만들 수 있다. 모든 영역에 테두리가 있도록 하려면 테두리를 그려야 하는 영역의 최소 개수는 얼마인가?

다음 예를 보자.

첫 번째 경우 최솟값은 3이다. 세 영역 모두 가장자리에 있으므로 세 영역 둘레에 테두리를 그리는 것 외에 다른 방법이 없다.
두 번째 경우 최솟값은 1이다. 0 영역 둘레에 테두리를 그리면 1 영역 둘레에도 테두리가 생긴다.
세 번째 경우 답은 8이다. 가장자리에 있는 모든 영역 둘레에 테두리를 그리면 가운데 영역 둘레에도 테두리가 생긴다.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어진다( $1 \le n, m \le 100$ ). $n$ 은 이미지의 행 수, $m$ 은 열 수이다.

다음 $n$ 개 줄에는 각각 길이 $m$ 인 문자열이 하나씩 주어지며, 문자 ‘0’과 ‘1’로만 이루어져 있다. 이 문자열이 이미지이다.

출력

모든 영역에 테두리가 있도록 하기 위해 테두리를 그려야 하는 영역 개수의 최솟값을 정수 하나로 출력한다.

예제3

예제 1
입력
```
3 3
000
111
000
```
예상 출력
```
3
```
예제 2
입력
```
3 3
000
010
000
```
예상 출력
```
1
```
예제 3
입력
```
3 3
010
101
010
```
예상 출력
```
8
```