[백준] 2140 : 지뢰찾기

문제 출처 : 2140번: 지뢰찾기 (acmicpc.net)

소요 시간 : 시도(65m, 실패) + 풀이(40m)

---

문제

---

시도

 

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

public class Main {

    static int N;
    static boolean[][] mineChecker;
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        read();

        findMind();

        printResult();
    }

    static void read() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        if (N <= 2) {
            System.out.println(0);
            System.exit(1);
        }

        mineChecker = new boolean[N][N];
    }

    static void findMind() throws IOException {

        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();

            for (int j = 0 ; j < N; j++) {
                if(chars[j] == '0'){
                    check(i, j);
                }
            }
        }
    }

    static void check(int i, int j) {

        for (int x = i - 1; x <= i + 1; x++) {
            if (x < 1 || x >= N - 1) continue;

            for (int y = j - 1; y <= j + 1; y++) {
                if (y < 1 || y >= N - 1) continue;

                mineChecker[x][y] = true;
            }
        }
    }

    static void printResult() {
        int mines = 0;

        for (int i = 1; i < N - 1; i++) {
            for (int j = 1; j < N - 1; j++) {
                if(mineChecker[i][j]) mines++;
            }
        }

        System.out.println((int) Math.pow(N-2, 2) - mines);
    }
}

---

풀이

 

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

public class Main {

    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 line = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N; j++) {
                if (Character.isDigit(map[i][j])) {
                    int current = map[i][j] - '0';
                    check(i, j, current);
                }
            }
        }

        int cnt = 0;
        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);
    }

    public static void check(int x, int y, int cur) {

        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 1 || ny < 1 || nx >= N || ny >= N) continue;

            if (cur != 0 && map[nx][ny] == '#') {
                cur--;
                map[nx][ny] = '*';
            } else if (cur != 0 && map[nx][ny] == '*') {
                cur--;
            } else if (cur == 0 && map[nx][ny] == '#')
                map[nx][ny] = '-';
        }
    }
}

---

회고

 

내가 시도한 방식은 0 만으로 지뢰가 없는 곳을 찾아 제거하려 했던 것이 문제.

 

다음과 같은 경우를 고려하지 못함 (윗 줄에 인접한 지뢰 칸에는 지뢰가 3 혹은 4 개가 존재할 수 있다.)

100

…11111111…

…#######…

 

때문에 테두리에 있는 숫자를 추적하여 그에 따라 지뢰 존재 여부를 판단하는, 풀이와 같은 로직이 필요했다.