백준 1996번 [지뢰 찾기](C++) -yes6686- 티스토리

백준 문제 풀이: 1996 (지뢰 찾기)

---

문제 링크: https://www.acmicpc.net/problem/1996

문제 설명:

지뢰찾기 게임에서 주어진 n × n 크기의 격자에서 각 칸에 대한 정보를 출력합니다. - 지뢰는 '*'로 표시됩니다. - 지뢰가 없는 칸에서는 인접한 8방향 칸에 포함된 지뢰의 수를 출력합니다. - 인접한 지뢰의 수가 10 이상이면 'M'으로 표시됩니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int arr[1001][1001];

// 8방향 이동을 위한 배열
int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 격자 입력 처리
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '.') {
                arr[i][j] = 0; // 지뢰가 없는 칸
            } else {
                arr[i][j] = s[j] - '0'; // 지뢰의 값
            }
        }
    }

    // 결과 계산 및 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] > 0) {
                cout << "*"; // 지뢰 칸은 '*'로 출력
            } else {
                int cnt = 0; // 인접한 지뢰의 합
                for (int t = 0; t < 8; t++) {
                    int nx = i + dx[t];
                    int ny = j + dy[t];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 격자 밖 무시
                    if (arr[nx][ny] > 0) {
                        cnt += arr[nx][ny];
                    }
                }
                // 출력 조건
                if (cnt >= 10) {
                    cout << "M";
                } else {
                    cout << cnt;
                }
            }
        }
        cout << '\n'; // 다음 행 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 주어진 지뢰 정보를 바탕으로 8방향 탐색을 통해 각 칸의 상태를 계산합니다.
• 구현 세부사항:
  • dx[], dy[]: 8방향 탐색을 위한 방향 벡터입니다.
  • 격자 탐색: 지뢰인 칸은 '*'로, 지뢰가 없는 칸은 인접 지뢰 합으로 표시합니다.
  • 인접 지뢰 합이 10 이상이면 'M'으로 표시합니다.
• 시간 복잡도 분석:
  • 격자를 순회하며 각 칸에서 최대 8방향을 탐색하므로 O(n²)입니다.
  • n의 최대값은 1000이므로 문제를 효율적으로 해결할 수 있습니다.

---

결과

격자의 각 칸에 대해 지뢰 여부와 인접 지뢰 합을 정확히 계산하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!