Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1868. 파핑파핑 지뢰찾기

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.

(문제 출처: SW Expert Academy)

  • Depth First Search를 이용하여 풀이하였다. 열 수 있는 칸들을 DFS로 접근하며 열어간다. 이 과정은 재귀적으로 이루어진다.
  • 지뢰를 심는 것과 동시에 칸에 적힐 숫자를 미리 구해두었다.
  • 임의의 칸을 열 때 칸에 적힌 숫자가 0이면 주변의 8칸 중 열린 적이 없는 칸들을 추가로 연다.
  • 최소의 횟수로 모든 칸을 여는 경우의 수를 구해야 하므로, 연쇄적으로 많은 칸을 열 수 있는 (숫자가 0인) 칸을 우선적으로 연다.
  • 지뢰 밭의 가로, 세로 길이 $N$은 최대 $300$이다. 즉, 모든 칸의 개수는 최대 $N^2 = 90,000$을 넘지 않는다.
    • 모든 칸을 초기화 하는데 $O(N^2)$의 시간이 걸린다.
    • 지뢰의 위치를 입력받아 지뢰 밭 위에 심는데 $O(N^2)$의 시간이 걸린다.
    • 모든 칸을 열어보는데 $O(N^2)$의 시간이 걸린다.
  • 테스트케이스당 시간 복잡도는 $O(N^2)$이다.
#include <iostream>
#define MAX_N 300

#define CELL_MINE '*'

using namespace std;

int number[MAX_N+1][MAX_N+1];
bool is_opened[MAX_N+1][MAX_N+1];
int board_size;

int n_clicks;

bool is_on_board(int y, int x) {
    return x >= 0 && y >= 0 && x < board_size & y < board_size;
}

void bury_mine(int y, int x) {
    int dy, dx;
    is_opened[y][x] = true;
    for (dx = -1; dx <= 1; dx++) {
        for (dy = -1; dy <= 1; dy++) {
            if (!is_on_board(y+dy, x+dx)) {
                continue;
            }
            number[y+dy][x+dx]++;
        }
    }
}

void open(int y, int x) {
    int dy, dx;
    if (!is_on_board(y, x) || is_opened[y][x]) {
        return;
    }
    is_opened[y][x] = true;
    if (number[y][x] > 0) {
        return;
    }
    for (dx = -1; dx <= 1; dx++) {
        for (dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0) {
                continue;
            }
            open(y+dy, x+dx);
        }
    }
}

void click(int y, int x) {
    n_clicks++;
    open(y, x);
}

void solve(int test_case_no)
{
    int y, x;
    char c;
    n_clicks = 0;
    // 모든 칸들을 초기화.
    cin >> board_size;
    for (y = 0; y < board_size; y++) {
        for (x = 0; x < board_size; x++) {
            number[y][x] = 0;
            is_opened[y][x] = false;
        }
    }
    // 지뢰의 위치를 입력 받아 지뢰 심기.
    for (y = 0; y < board_size; y++) {
        for (x = 0; x < board_size; x++) {
            cin >> c;
            if (c == CELL_MINE) {
                bury_mine(y, x);
            }
        }
    }
    // 숫자가 0인 칸들을 우선 클릭 함.
    for (y = 0; y < board_size; y++) {
        for (x = 0; x < board_size; x++) {
            if (!is_opened[y][x] && number[y][x] == 0) {
                click(y, x);
            }
        }
    }
    // 나머지 칸들을 클릭 함.
    for (y = 0; y < board_size; y++) {
        for (x = 0; x < board_size; x++) {
            if (!is_opened[y][x]) {
                click(y, x);
            }
        }
    }
    printf("#%d %d\n", test_case_no, n_clicks);
}

int main(int argc, char **argv)
{
    int T;
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> T;
    for (int test_case_no = 1; test_case_no <= T; ++test_case_no)
    {
        solve(test_case_no);
    }
    return 0;
}

Back to top