[백준] 1303번: 전쟁 - 전투 / C++

✏️ 문제 링크

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

1303번: 전쟁 - 전투

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 코드(bfs)

#include <bits/stdc++.h>

using namespace std;
char field[101][101];
bool vis[101][101];

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

int N, M, W, B; 

int bfs(int i, int j, char c){
    int cnt=0;
    queue<pair<int, int>> q;
    q.push({i, j});
    vis[i][j]=true;
    
    while(!q.empty()){
        int x=q.front().first; int y=q.front().second;
        q.pop();
        cnt++;
        for(int k=0; k<4; k++){
            int nx=x+dx[k]; int ny=y+dy[k];
            if(nx<0 || nx>=M || ny<0 || ny>=N || vis[nx][ny]) continue;
            if(field[nx][ny]==c){
                vis[nx][ny]=true;
                q.push({nx, ny});
            }
        }
    }
    return cnt;
}

int main(){
    cin>>N>>M;
    W=B=0;
    
    for(int i=0; i<M; i++){
        string s; cin>>s;
        for(int j=0; j<N; j++){
            field[i][j]=s[j];
            vis[i][j]=false;
        }
    }
    
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(!vis[i][j]){
                int cc=0;
                if(field[i][j]=='W'){
                    cc+=bfs(i, j,'W');
                    W+=cc*cc;
                }else{
                    cc+=bfs(i, j, 'B');
                    B+=cc*cc;
                }
            }
        }
    }
    cout<<W<<" "<<B;

    return 0;
}

 

✏️ 문제 코드(dfs)

#include <iostream>

using namespace std;
int N, M;
char field[101][101];
bool vis[101][101];
int cnt=0;
int dx[]={-1, 1, 0,0};
int dy[]={ 0,0,-1, 1,};
void dfs(int x, int y, char c){
    vis[x][y]=true;
    
    for(int i=0; i<4; i++){
        int nx = x+dx[i]; int ny = y+ dy[i];

        if(nx<0|| nx>=N|| ny<0|| ny>=M)continue;
        if(!vis[nx][ny] && field[nx][ny]==c){
            cnt++;
            dfs(nx, ny, c);
        }
    }
}
int main()
{
    int W=0, B=0;
    
    cin>>M>>N;
    for(int i=0; i<N; i++){
        string s; cin>>s;
        for(int j=0; j<M; j++){
            field[i][j]=s[j];
            vis[i][j]=false;
        }
    }
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(!vis[i][j]){
                cnt=1;
                dfs(i, j, field[i][j]);
                if(field[i][j]=='W'){W+=(cnt*cnt);}
                else B+=(cnt*cnt);
            }
        }
    }
    
    cout<<W<<" "<<B;
    return 0;
}

 

 

 ⭐ if feedback and question : comment please⭐