[코드업] 3500 : 지뢰 찾기 2 (C)

알고리즘 : DFS, Flood Fill

풀이

단순한 탐색 알고리즘 문제지만 다른 문제들과 다른점은 4방향이 아닌 8방향을 탐색해야 한다는 것이다. 방향배열을 8*2로 잡아주고 탐색을 해주면 된다.

문제를 풀기에 앞서 이해를 해보면 다음과 같다.

1. 특정 칸의 숫자는 그 칸 주위의 8개의 칸 중에 지뢰의 개수를 나타낸다.
2. 클릭한 칸에서 시작하여 (1)의 숫자가 0이 아닐때 까지 탐색한다. (이때 탐색도 8방향이다) 탐
3. 탐색한 칸은 (1)의 숫자, 탐색하지 않은 칸은 _로 출력한다.
4. 내가 선택한 칸이 지뢰일 경우 그 칸을 -1 나머지는 _를 출력한다.

in배열은 입력 데이터 이고 map배열은 지뢰의 갯수를 세어 놓는 배열이다. ( 탐색이 끝나는 지점이 될 것이다. ) 처음에 in 배열을 모두 돌아 map 배열을 채워준다. map을 채울때는 배열의 크기를 넉넉하게 잡고 (배열의 범위를 초과하지 않도록) 주위 8개의 in배열의 원소를 더해주면 된다. 그 뒤 Flood Fill을 해주는데 확인 해준 인덱스에 대해서는 check 배열에 표시를 해준다. 출력 할 때는 해당 인덱스가 check배열에 표시가 되어있다면 탐색을 한 것이므로 map배열의 해당 값을, 아니라면 _를 출력 해준다.

#include<iostream>
using namespace std;
int in[11][11];
int map[10][10];
int check[10][10];
int dir[8][2]={{1,0},{0,1},{0,-1},{-1,0},{-1,1},{1,1},{-1,-1},{1,-1}};

void dfs(int a, int b){
    check[a][b]=1;

    if(map[a][b]!=0)
        return;

    for(int i=0;i<8;i++){
        int na = a+dir[i][0], nb = b+dir[i][1];
        if(na<1||nb<1||na>9||nb>9||check[na][nb])
            continue;
        dfs(na,nb);
    }
}

int main(){
    int a,b;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++)
            cin>>in[i][j];
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            map[i][j]=in[i-1][j-1]+in[i][j-1]+in[i-1][j]
            +in[i+1][j+1]+in[i+1][j]+in[i][j+1]+in[i-1][j+1]+in[i+1][j-1];
        }    
    }

    cin>>a>>b;

    if(in[a][b]==1){
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                if(j==a&&b==i)
                    cout<<"-1 ";
                else
                    cout<<"_ ";
            }
            cout<<"\n";
        }
        return 0;
    }

    dfs(a,b);

    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(check[i][j])
                cout<<map[i][j]<<" ";
            else
                cout<<"_ ";
        }    
        cout<<"\n";
    }

}

 

 

제출 결과