[cpp 알고리즘] 백준 4396 지뢰 찾기

[백준] 4396 지뢰 찾기 cpp 풀이

알고리즘: 구현

https://www.acmicpc.net/problem/4396

 

문제 요약

N*N의 지뢰 판이 주어지고, M개의 지뢰가 있다. 

- 입력1) 온점(.)은 지뢰가 없고, 별표(*)는 지뢰가 있는 지점이다.

- 입력2) 이미 열린 칸은 영소문자x로, 열리지 않은 칸은 온점(.)으로 표시된다. 

- 출력) (1) 지뢰가 없으면서 열린 칸은 0~8 사이의 숫자, (2) 지뢰가 있는 칸이 열렸으면 지뢰가 있는 모든 칸을 별표(*)로, (3) 다른 모든 지점은 온점(.) 으로 표현해야 한다. 

문제를 이해하는 것과 주어진 테스트코드로 이해는 쉬웠으나, 몇 가지 경우에 대해 더 생각해 봐야 한다...😒

풀이 정리

(1) 우선 N*N의 기본 지뢰 판을 만들고, 온점(.)과 별표(*)로 지뢰가 있는 지점을 표시해둔다. => arr 배열

(2) 이미 열린 칸은 x로, 열리지 않은 칸은 온점(.)으로 들어오는데, 이 때 크게 아래와 같이 나눌 수 있다.

1. 이미 열린 칸(x) 중에, 지뢰가 아닌 경우 => 0~8로 주변에 있는 지뢰 개수를 나타내면 된다.
2. 이미 열린 칸(x) 중에, 지뢰인 경우 => 지뢰가 있는 모든 칸을 별표(*)로 나타내면 된다.
3. 열리지 않은 칸(.)의 경우 => 온점(.)으로 나타내면 된다. 

(3) 나는 newarr 배열을 온점(.)으로 초기화하고, 이미 열린 칸에 대해서만 처리해주는 식으로 코드를 구현했다. 

C++ 코드

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

int N;

char arr[11][11];
char newarr[11][11];

int dx[8] = {1,-1,0,0,1,1,-1,-1};
int dy[8] = {0,0,1,-1,1,-1,1,-1};

void check(int y, int x){
    int bomb = 0;
    for(int i=0; i<8; i++){
        int ny = y+dy[i]; int nx = x+dx[i];
        if(arr[ny][nx] == '*') bomb++;
    }
    char tmp = '0';
    newarr[y][x] = tmp+bomb;
}

int main(){
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> arr[i][j];
            newarr[i][j] = '.';
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            char c; cin >> c;
            if(c=='x' && arr[i][j] == '.'){
                check(i,j);
            }
            else if(c=='x' && arr[i][j] == '*'){
                for(int y=0; y<N; y++){
                    for(int x=0; x<N; x++){
                        if(arr[y][x] == '*') {
                            newarr[y][x] = '*';
                        }
                    }
                }
            }
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cout << newarr[i][j];
        }
        cout << "\n";
    }
    
    return 0;
}

 

문제가 헷갈렸다면?

이 게임을 안해봐서 그런지 문제 자체를 이해하는 것은 쉬웠지만, 몇 가지 애매한 요소들이 있었던 것 같다. 

 (1) 지뢰를 밟았을 때, 이전에 열린 지뢰 없는 칸 혹은 이후에 열린 지뢰 없는 칸 들은 모두 지뢰 개수(0~8사이의 값) 으로 나타내줘야 한다.

 (2),(3) 지뢰를 밟았을 때, 모든 지뢰가 출력되어야 한다. 

위의 각각 사항들을 확인하기 위한 추가 테스트 케이스이다. 

추가 테스트 케이스

입력(1) 

8

...**..*
......*.
....*...
........
........
.....*..
...**.*.
.....*..
xxxx....
....xxxx
xxxx....
....xxxx
xxxx....
....xxxx
xxxx....
....xxxx

 

출력(1) 

001**..*
....33*2
0001*...
....1100
0000....
....3*21
001**.*.
....3*21

 

입력(2) 

2

*.
.*
..
.x

 

출력(2) 

*.
.*

 

입력(3)

2

**
**
x.
..

 

출력(3) 

**
**