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

백준 문제 풀이: 4396 [지뢰 찾기]

---

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

문제 설명:

지뢰가 있는 게임판에서 사용자의 클릭 결과를 바탕으로 지뢰찾기 게임의 결과를 출력하는 문제입니다.

입력은 두 개의 n×n 게임판으로 주어집니다:

• 첫 번째 게임판: 지뢰가 있는 위치를 나타냄. *는 지뢰, .는 지뢰가 없음.
• 두 번째 게임판: 사용자의 클릭 결과를 나타냄. x는 클릭한 칸, .는 클릭하지 않은 칸.

게임판을 출력할 때 다음 조건을 따릅니다:

• 지뢰가 있는 칸이 클릭되면 모든 지뢰를 표시합니다.
• 클릭한 칸이 지뢰가 아니면 주변 8방향에 있는 지뢰의 개수를 표시합니다.
• 클릭하지 않은 칸은 그대로 .로 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr1[11][11]; // 지뢰 위치 저장
int arr2[11][11]; // 사용자 입력 저장

int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 8방향 이동
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 < n; j++) {
            arr1[i][j] = (s[j] == '*') ? 1 : 0;
        }
    }

    int check = 0; // 지뢰가 클릭되었는지 여부
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '.') {
                arr2[i][j] = -1; // 클릭하지 않은 칸
            } else if (arr1[i][j] == 1) {
                arr2[i][j] = -2; // 지뢰가 있는 칸이 클릭됨
                check = 1;       // 지뢰가 클릭되었음을 표시
            } else { // 클릭된 칸
                int cnt = 0;
                for (int t = 0; t < 8; t++) { // 주변 8칸 탐색
                    int nx = i + dx[t];
                    int ny = j + dy[t];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < n && arr1[nx][ny] == 1) {
                        cnt++;
                    }
                }
                arr2[i][j] = cnt; // 주변 지뢰 개수 저장
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check == 1 && arr1[i][j] == 1) {
                cout << "*"; // 지뢰가 클릭된 경우 모든 지뢰 표시
            } else if (arr2[i][j] == -1) {
                cout << "."; // 클릭하지 않은 칸
            } else if (arr2[i][j] == -2) {
                cout << "*"; // 클릭된 지뢰
            } else {
                cout << arr2[i][j]; // 주변 지뢰 개수 출력
            }
        }
        cout << '\n';
    }

    return 0;
}

---

코드 설명

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

• 지뢰 위치 입력: 첫 번째 게임판을 입력받아 arr1에 지뢰 위치를 저장합니다.
• 사용자 클릭 결과 처리:
  • 클릭된 칸(x)이 지뢰(*)이면 check를 1로 설정합니다.
  • 클릭된 칸이 지뢰가 아니면 8방향을 탐색해 주변 지뢰의 개수를 계산합니다.
• 결과 출력:
  • 지뢰가 클릭된 경우 모든 지뢰를 표시합니다.
  • 클릭되지 않은 칸은 그대로 .로 출력합니다.
  • 클릭된 칸은 주변 지뢰의 개수를 출력합니다.

---

시간 복잡도 분석

• 게임판의 크기를 \(n \times n\)이라 하면, 각 칸에서 최대 8방향을 탐색하므로 전체 시간 복잡도는 \(O(n^2)\)입니다.

---

결과

주어진 게임판에서 사용자의 클릭 결과를 바탕으로 지뢰찾기 게임의 결과를 정확히 출력합니다. 클릭된 지뢰가 있는 경우 모든 지뢰를 표시하며, 그렇지 않은 경우 주변 지뢰의 개수를 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!