[백준]#2140 지뢰찾기

문제

지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는지에 대한 정보가 주어진다. 게이머는 게임을 진행하면서 보드의 칸을 하나씩 열게 된다. 만약 그 칸에 지뢰가 있다면 게임이 끝나고, 없는 경우에는 그 칸에 적혀있는 숫자, 즉 그 칸과 인접해 있는 8개의 칸들 중 몇 개의 칸에 지뢰가 있는지를 알 수 있게 된다.

이 문제는 보드의 테두리가 모두 열려있고, 그 외는 모두 닫혀있는 상태에서 시작한다. 예를 들어 다음과 같은 경우를 보자.

1	1	1	0	0
2	#	#	#	1
3	#	#	#	1
2	#	#	#	1
1	2	2	1	0

#는 닫혀있는 칸을 나타낸다. 이러한 보드가 주어졌을 때, 닫혀있는 칸들 중 최대 몇 개의 칸에 지뢰가 묻혀있는지 알아내는 프로그램을 작성하시오. 위의 예와 같은 경우에는 다음과 같이 6개의 지뢰가 묻혀있을 수 있다.

1	1	1	0	0
2	*			1
3	*	*	*	1
2	*	*		1
1	2	2	1	0

입력

첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 N개의 문자가 공백 없이 주어지는데, 이는 게임 보드를 의미한다.

출력

첫째 줄에 묻혀있을 수 있는 지뢰의 최대 개수를 출력한다.

예제 입력 1

5
11100
2###1
3###1
2###1
12210

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

풀이

이 문제는 단순 구현을 통해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int[][] map;
    static int N;
    static int[] dx = {0, 1, -1, 0, 1, 1, -1, -1};
    static int[] dy = {1, 0, 0, -1, 1, -1, 1, -1};    //상하좌우,대각선 8방향

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i=0; i<N; i++) {
            String input = br.readLine();
            for(int j=0; j<N; j++) {
                map[i][j] = input.charAt(j)- '0';
            }
        }

        if(N<3) {             //N<3인경우 무조건 0
            System.out.println(0);
            return;
        }

        int ans = sol();

        System.out.println(ans);
    }

    public static int sol() {
        int cnt = 0;

        for(int i=1; i<N-1; i++) {
            loop:for(int j=1; j<N-1; j++) {
                for(int k=0; k<8; k++) {    //8방향 체크
                    int nx = i+dx[k];
                    int ny = j+dy[k];

                    if(map[nx][ny]>3) continue;   //닫힌 곳이면 그냥 넘어감

                    if(map[nx][ny]==0) continue loop;   //지뢰가 있을 수 없는 곳
                }

                for(int k=0; k<8; k++) {      //지뢰가 있을 수 있는 곳이면 테두리 숫자 하나씩 빼줌
                    int nx = i+dx[k];
                    int ny = j+dy[k];

                    if(map[nx][ny]<=3)
                        map[nx][ny]--;
                }

                cnt++;      //지뢰 하나씩 증가
            }
        }

        return cnt;
    }
}