[백준] 2140번 지뢰찾기 (자바 풀이)

문제

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

2140번: 지뢰찾기

 

풀이

이 문제는 구현 + 그리디 알고리즘 문제이다. 배열의 테두리에서 지뢰를 넣을 수 있는 곳을 모두 체크해야 한다.

이때 8방향을 조사해서 지뢰를 넣을 수 있는 곳은 '*'로 표시해두고, 넣을 수 없는 곳이라면 '-'로 표시해두었다.

또한 이미 '*'로 표시되어 있다면 넣을 수 있는 지뢰의 개수를 1씩 감소시켰다.

 

마지막에 '*' 개수를 세고, 주의해야 할 점은 '#'으로 남아 있는 부분도 count 해야 한다는 점이다. '#'으로 남아있는 부분은 지뢰를 무조건 넣을 수 있는 부분이기 때문에 이 부분도 정답에 포함시키면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Baekjoon_2140 {
    static int N;
    static char map[][];
    static int dx[] = {-1,-1,-1,0,0,1,1,1};
    static int dy[] = {-1,0,1,-1,1,-1,0,1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N;j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        int cnt = 0;
        /* 지뢰 위치 탐색 */
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(Character.isDigit(map[i][j])) {
                    int cur = map[i][j]-'0';
                    check(i,j, cur);    
                }
            }
        }
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                // 지뢰를 넣었거나 넣을 수 있다면
                if(map[i][j] == '*' || map[i][j] == '#') {    
                    cnt++;
                }
            } 
        }
        System.out.println(cnt);
    }
    
    /* 8방향 체크 */
    public static void check(int x, int y, int cur) {
        
        for(int i=0; i<8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx<0 || ny<0 || nx >=N || ny >=N ) continue;
            
            if(map[nx][ny] == '#' && cur != 0) {    // 지뢰를 넣을 수 있다면
                cur--;
                map[nx][ny] = '*';
            }else if(map[nx][ny] == '*' && cur != 0) {    // 이미 지뢰가 있다면
                cur--;
            }else if(map[nx][ny] == '#' && cur == 0) {    // 지뢰를 넣을 수 없다면
                map[nx][ny] = '-';
            }    
        }
    }
}