백준 2140 (지뢰찾기) - java

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

2140번: 지뢰찾기

 

문제

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

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

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

유형 : 그리디 + 탐색

 

접근 방식

• 8방 탐색을 해서 주변의 정보를 갱신한다.
• #인 위치는 애초에 숫자를 9로 입력하여 주변에 의해 숫자가 깍여도 1이상을 항상 유지하끔한다.

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int[][] board;

    static int[] dx = {0,0,1,-1,1,1,-1,-1};
    static int[] dy = {1,-1,0,0,1,-1,1,-1}; // 8방 탐색

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());

        board = new int[n+1][n+1];

        for(int i=1;i<=n;i++){
            String line = bf.readLine();

            for(int j=1;j<=n;j++){
                char tmp = line.charAt(j-1);

                if(tmp == '#')
                    board[i][j] = 9; // 가능한 위치는 9로 설정

                else
                    board[i][j] = tmp - '0';
            }
        }

        int count = 0;

        for(int i=2;i<=n-1;i++){
             for(int j=2;j<=n-1;j++){

                boolean can = true;

                for(int k=0;k<8;k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if(board[nx][ny] == 0) {
                        can = false; // 지뢰가 존재할 수 없는 위치
                        break;
                    }
                }

                if(can){
                    for(int k=0;k<8;k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        board[nx][ny] -= 1; // 해당 위치에 지뢰를 박을것이기 때문에 주변의 정보 -1
                    } 

                    count++; // 지뢰 개수 증가
                }
            }
        }

        System.out.println(count);

        bf.close();
    }
}