[SWEA] 1868 - 파핑파핑 지뢰찾기

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 삼성 SW Expert Academy의 1868번 문제인 파핑파핑 지뢰찾기에 대해 알아보도록 하겠습니다.

 

 

 

접근 방법

해당 문제는 실제 지뢰찾기와 유사한 로직을 가지고 있습니다. 바로 0인 칸을 누르면 연쇄작용이 일어난다는 점입니다. 그 외에 특이사항으로는 지뢰가 어디 있는지 미리 알고 있다는 것과, 지뢰를 제외한 나머지 모든 칸을 오픈하기 위해 필요한 최소 클릭 횟수를 구하는 정도겠네요.

제가 생각하는 키 포인트는 다음과 같습니다.

• 값이 0인 칸들의 목록 : 최소 횟수를 구하기 위해, 보드를 스캔 후 값이 0인 칸들의 좌표 목록을 만듭니다. 해당 좌표에 해당하는 칸들을 모두 클릭(오픈)하면, 값이 1 이상인 칸들만 남게 됩니다.
• 값이 0이 아닌 칸들의 목록 : 최소 횟수를 구하기 이ㅜ해, 보드를 스캔 후 값이 0이 아닌 칸들의 좌표 목록을 만듭니다. 값이 0인 칸을 클릭하면 자동으로 주변 칸까지 확장되므로, 아직 열리지 않은 나머지 칸들을 하나씩 눌러야 합니다.
• DFS or BFS : 값이 0인 칸을 오픈하면, 주변으로 확장되어야 합니다. 이를 위해 DFS 혹은 BFS를 사용합니다.

 

 

최소 클릭 횟수

처음에는 모든 칸을 일일이 눌러보고 최소 회수가 아니라면 이전 상태로 돌아가는 백트래킹을 써볼까 하다가, 굳이 그럴 필요가 있는가 싶어서 위와 같은 로직으로 구현을 했습니다. 위 로직이 가능한 이유는 보드의 정보를 미리 알고 있기 때문입니다.

또한 값이 0인 칸이 뭉쳐 있는 경우, 해당 그룹에서 아무 칸이나 눌러도 최소 횟수에 변동은 없습니다. 따라서 그룹 내 어느 칸을 눌러야 할 지 고민하지 않아도 됩니다. (매우매우 고마운 부분..)

 

 

풀이 코드 (java)

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

public class Q1868 {
    TestCase[] testCases;
    ArrayList<Point> zeroPoints = new ArrayList<>();
    ArrayList<Point> nonZeroPoints = new ArrayList<>();
    int openCount = 0;

    public void main() {
        scanBoardList();

        for (int i = 0; i < this.testCases.length; i++) {
            getZeroPointsAndNonzeroPoints(this.testCases[i]);
            final int finalI = i;
            this.zeroPoints.forEach(point -> open(this.testCases[finalI], point.row, point.column, true, false));
            this.nonZeroPoints.forEach(point -> open(this.testCases[finalI], point.row, point.column, false, false));
            System.out.println(String.format("#%d %d", finalI + 1, this.openCount));

            this.openCount = 0;
        }
    }

    private Point[] getNeighborhoods(int r, int c) {
        Point[] neighborhoods = new Point[8];
        neighborhoods[0] = new Point(r - 1, c);
        neighborhoods[1] = new Point(r - 1, c + 1);
        neighborhoods[2] = new Point(r, c + 1);
        neighborhoods[3] = new Point(r + 1, c + 1);
        neighborhoods[4] = new Point(r + 1, c);
        neighborhoods[5] = new Point(r + 1, c - 1);
        neighborhoods[6] = new Point(r, c - 1);
        neighborhoods[7] = new Point(r - 1, c - 1);
        return neighborhoods;
    }

    private void scanBoardList() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        try {
            int testCaseNumber = Integer.parseInt(br.readLine(), 10);
            testCases = new TestCase[testCaseNumber];

            for (int i = 0; i < testCaseNumber; i++) {
                int boardSize = Integer.parseInt(br.readLine(), 10);
                testCases[i] = new TestCase(boardSize);

                for (int j = 0; j < boardSize; j++) {
                    char[] row = br.readLine().toCharArray();
                    System.arraycopy(row, 0, testCases[i].board[j], 0, boardSize);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void printBoardList() {
        for (TestCase testCase : testCases) {
            for (char[] row : testCase.board) {
                System.out.println(row);
            }
        }
    }

    private void getZeroPointsAndNonzeroPoints(TestCase testCase) {
        for (int r = 0; r < testCase.board.length; r++) {
            for (int c = 0; c < testCase.board.length; c++) {
                if (testCase.board[r][c] == '*') continue;
                int boxValue = getBoxValue(testCase, r, c);
                if (boxValue == 0) this.zeroPoints.add(new Point(r, c));
                else this.nonZeroPoints.add(new Point(r, c));
            }
        }
    }

    private int getBoxValue(TestCase testCase, int r, int c) {
        int count = 0;

        for (Point neighbor : getNeighborhoods(r, c)) {
            try {
                if (testCase.board[neighbor.row][neighbor.column] == '*') count++;
            } catch (ArrayIndexOutOfBoundsException e) {
            }
        }

        return count;
    }

    private void open(TestCase testCase, int r, int c, boolean isZero, boolean isPropagated) {
        if (r < 0 || c < 0 || r > testCase.board.length || c > testCase.board.length) return;
        if (testCase.board[r][c] == '*') return;
        if (testCase.board[r][c] == '.') {
            if (!isPropagated) this.openCount++;
            if (!isZero) testCase.board[r][c] = Character.forDigit(getBoxValue(testCase, r, c), 10);
            else {
                testCase.board[r][c] = '0';

                for (Point neighbor : getNeighborhoods(r, c)) {
                    try {
                        open(testCase, neighbor.row, neighbor.column, false, true);
                    } catch (ArrayIndexOutOfBoundsException e) {
                    }
                }
            }
        }
    }
}

class TestCase {
    char[][] board;

    TestCase(int N) {
        this.board = new char[N][N];
    }
}

class Point {
    int row;
    int column;

    Point(int r, int c) {
        this.row = r;
        this.column = c;
    }
}

로직은 다음과 같습니다.

1. 입력으로부터 testCases를 만듭니다.
2. testCases에 대해, 문제 풀이를 시작합니다.
3. 특정 testCase의 board를 기반으로 값이 0인 칸들의 좌표 목록(zeroPoints)과 값이 0이 아닌 칸들의 좌표 목록(nonZeroPoints)를 구합니다.
4. zeroPoints에 대해, 오픈을 합니다.
5. nonZeroPoints에 대해, 오픈을 합니다.
6. openCount를 출력합니다.

참고로 위 풀이 코드는 memory error가 납니다..