[SW Expert] #1868 파핑파핑 지뢰찾기

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

먼저 NXN Array를 지뢰 = -1 나머지 칸은 숫자로 바꾼 Change_Array를 만들고 바꾼 Change_Array의 값이 0이고, 방문 안 한 곳을 체크하게 하고, 문제 의도대로 8방향으로 dfs 하였다. 이후 값이 0과 -1 이아닌 값들 중 방문하지 않은 개수만큼 개수를 추가해주는 방법으로 해결하였다

---

2. 코드

코드는 다음과 같다

#include<iostream>
#include<string.h>
using namespace std;
	int T;
    int N;
char array[300][300];
int change_array[300][300];
bool chk_array[300][300];
int count = 0;
int dx[8] = {-1, 0, 1, -1, 1, -1, 0 ,1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void change(){
     for(int i = 0; i < N; i++){         
        	for(int j = 0; j < N; j++){
				if(array[i][j] == '*') change_array[i][j] = -1;
                else{
                    int cnt = 0;
                    for(int k = 0; k < 8; k++){
                     	int nx = i + dx[k];
                     	int ny = j + dy[k];
                        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                        if(array[nx][ny] == '*') cnt++;
                    }
                    change_array[i][j] = cnt;
                }
            }
        }
}

void dfs(int x, int y){
    chk_array[x][y] = true;
    
    for(int k = 0; k < 8; k++){
    	int nx = x + dx[k];
        int ny = y + dy[k];
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        else{
         	if(change_array[nx][ny] == 0 && !chk_array[nx][ny]){
             	dfs(nx, ny);   
            }else{
             	chk_array[nx][ny] = true;   
            }
        }
    }
}

int main(int argc, char** argv)
{

	cin >> T;
    for(int i = 0; i < T; i++){
        count = 0;
         memset(array, 0, sizeof(array));
         memset(change_array, 0, sizeof(change_array));
         memset(chk_array, 0, sizeof(chk_array));
        
        cin >> N;
        for(int j = 0; j < N; j++){
        	for(int k = 0; k < N; k++){
            	cin >> array[j][k];
            }
        }
        change();
        
        for(int j = 0; j < N; j++){
        	for(int k = 0; k < N; k++){
                if(change_array[j][k] == 0 && !chk_array[j][k]){
                    count++;
                 	dfs(j,k);
                }
            }
        }
        
        for(int j = 0; j < N; j++){
        	for(int k = 0; k < N; k++){
                if(change_array[j][k] != 0 && !chk_array[j][k] && change_array[j][k] != -1 ){
					count ++;
                }
            }
        }
        	cout << "#" <<i+1<<" "<<count<<endl;
    }
}