[SWEA] 1868. 파핑파핑 지뢰찾기(c++) / bfs

비교적? 간단한 bfs문제이다.

지뢰가 없는 곳을 방문하고 그와 인접한 8곳 중에서도 지뢰가 없다면 bfs로 방문처리를 한다.

그리고 최종적으로 방문하지 못한 곳 중 지뢰가 없는 곳을 세어주면 값을 구할 수 있다.

 

코드 첨부

// 1868. 파핑파핑 지뢰찾기
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
int testcase, n;
string s;
char game[301][301];
int visited[301][301] = {0, };
int dx[8] = {0, 0, -1, 1, -1, 1, -1, 1};
int dy[8] = {-1, 1, 0, 0, -1, 1, 1, -1};
int num = 0;
 
// 주위 8칸에 모두 지뢰가 없는지 확인
bool check(int x, int y)
{
    for(int i=0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(0<=nx && nx<n && 0<=ny && ny<n){
            if(game[nx][ny]=='*'){
                return false;
            }
        }
    }
    return true;
}   
 
void play()
{
    // 주위 8칸에 지뢰가 없는 빈칸을 찾는다.
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j] && game[i][j]=='.' && check(i, j)){
                num++;
                // visited[i][j] = 1;
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
 
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    visited[x][y] = 1;
                    q.pop();
 
                    for(int k=0; k<8; k++){
                        int nx = x+dx[k];
                        int ny = y+dy[k];
                        if(0<=nx && nx<n && 0<=ny && ny<n && !visited[nx][ny] && game[nx][ny]=='.'){
                            visited[nx][ny] = 1;
                            if(check(nx, ny)){ // 주위에 8칸에 지뢰가 없는 곳
                                q.push(make_pair(nx, ny));
                            }
                        }
                    }
                }
            }
        }
    }
}
 
int main()
{
    cin>>testcase;
    for(int i=0; i<testcase; i++){
        num = 0;
        memset(visited, 0, sizeof(visited));
        cin>>n;
        for(int j=0; j<n; j++){
            cin>>s;
            for(int k=0; k<s.size(); k++){
                game[j][k] = s[k];
            }
        }
 
        play();
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                if(!visited[j][k] && game[j][k]=='.'){
                    num++;
                }
            }
        }
        cout<<"#"<<i+1<<" "<<num<<"\n";
    }
}
 

 

 

문제 첨부

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc

SW Expert Academy