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

1. 시작점이 여러개인 경우

2. 거리 계산

두가지를 할 수 있으면 풀 수 있는 문제 같다.

1번의 경우 이중 for문으로 모든 정점을 돌며 시작점을 찾으며 bfs를 진행하면 되고,
2번의 경우 시작점을 기준으로 큐안에 들어가는 정점의 갯수를 세면 된다.

 

그리고 W,B의 경우를 각각 구하기 위해 BFS를 두번 구하였다.

#include <bits/stdc++.h>
using namespace std;

int n,m;
string board[102];
int vis[102][102];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>board[i];
    }
    //bfs를 크게 두번 돌리면 되지 않을까
    //W의 경우
    int w_num=0;
    int b_num=0;
    int w_sum=0;
    int b_sum=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(board[i][j]=='B'||vis[i][j]==1) continue;
            queue<pair<int,int>> q;
            vis[i][j]=1;
            q.push({i,j});
            w_num=0;
            while(!q.empty()){
                w_num++;
                auto cur=q.front();
                q.pop();
                for(int dir=0;dir<4;dir++){
                    int nx=cur.first+dx[dir];
                    int ny=cur.second+dy[dir];
                    if(nx<0||ny<0||nx>=m||ny>=n) continue;
                    if(vis[nx][ny]==1||board[nx][ny]=='B') continue;
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
            w_sum+=w_num*w_num;
        }
    }
        //B의 경우
        for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(board[i][j]=='W'||vis[i][j]==1) continue;
            queue<pair<int,int>> q;
            vis[i][j]=1;
            q.push({i,j});
            b_num=0;
            while(!q.empty()){
                b_num++;
                auto cur=q.front();
                q.pop();
                for(int dir=0;dir<4;dir++){
                    int nx=cur.first+dx[dir];
                    int ny=cur.second+dy[dir];
                    if(nx<0||ny<0||nx>=m||ny>=n) continue;
                    if(vis[nx][ny]==1||board[nx][ny]=='W') continue;
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
            b_sum+=b_num*b_num;
        }
    }
    cout<<w_sum<<" "<<b_sum;
}

1