백준 2140. 지뢰찾기

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

2140번: 지뢰찾기

 

우선 주어지는 태두리의 값만으로는 모든 칸들을 정확히 판별할수는 없다.

그런데 문제에서  닫혀있는 칸들 중 최대 몇 개의 칸에 지뢰가 묻혀있는지 알아내라고 했으므로 우선 모든 닫힌 칸들이 지뢰라고 가정한다.

 

우선 칸들의 상태를 3가지로 나눈다.

-1 : 불확실한 칸 

0 : 지뢰 확정인 칸 

1 : 지뢰 아닌 것이 확정인 칸 

 

그 후 열려있는 태두리 칸들을 돌면서 닫힌 칸들의 상태에 따라 케이스를 나눈다.

1. 주위 지뢰 확정인 칸 수와 주위 지뢰 예상 수(주어지는 보드판의 숫자)가 같다면, 나머지 불확실한 칸들은 모두 지뢰가 아닌것이 확정이다.

2. 주위 불확실한 칸 수와 주위 예상 지뢰수가 같다면, 모든 불확실한 칸은 지뢰인것이 확정이다.

3. 주위 불확실한 칸 수 + 주위 확정 지뢰수가 주위 예상 지뢰수와 같다면, 모든 불확실한 칸 은 지뢰가 확정이다.

 

이렇게 해서 최초에 닫혀 있는 칸 - 지뢰가 아닌 것이 확정인 칸 이 지뢰가 묻혀있을수 있는 칸이다.