백준 1303 전쟁 C++

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

1303번: 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

---

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

---

W와 B의 개수를 따로 세줘야 한다.

W를 검사하는 DFS함수와 B를 검사하는 DFS함수를 따로 만들어주고, 각각 DFS를 돌고 한 영역들

W로 이어지는 영역, B로 이어지는 영역을 한번 찾고 나면 vector w,vector b에 각각 영역에 있는 W,B의 개수를 제곱해서 넣어주고

마지막에는 W,B각각의 벡터에 있는 값들을 더해주면 해결할 수 있었다.

---

#include <iostream>
#include <vector>
#define MAX 101
using namespace std;
char map[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int n,m;
int B = 1;
int W = 1;
 
vector<int> b; // B,W 위력의 합을 저장할 각각의 벡터
vector<int> w;
void init(){ //방문배열 초기화 함수
    for(int i = 0;i<MAX;i++){
        for(int j = 0;j<MAX;j++){
            visited[i][j] = false;
        }
    }
}
void dfs_W(int x,int y){ //W만 찾아서 검사하는 함수(찾을 때마다 W값 ++)
 
    visited[x][y] = true;
    for(int i = 0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m){
            continue;
        }
        if(visited[nx][ny] == false && map[nx][ny] == 'W'){
            W++;
            dfs_W(nx,ny);
        }
    }
}
 
void dfs_B(int x,int y){ //B만 찾아서 검사하는 함수(찾을 때마다 B값 ++)
 
    visited[x][y] = true;
    for(int i = 0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m){
            continue;
        }
        if(visited[nx][ny] == false && map[nx][ny] == 'B'){
            B++;
            dfs_B(nx,ny);
        }
    }
}
 
int main(void){
    cin >> m >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> map[i][j];
        }
    }
 
    for(int i = 0;i<n;i++){ //W만 찾아보기
        for(int j = 0;j<m;j++){
            if(visited[i][j] == false && map[i][j] == 'W'){
                dfs_W(i,j);
                w.push_back((W)*(W));
                W = 1;
 
            }
        }
    }
    init(); //B찾기 전 초기화 함수 돌리고
 
    for(int i = 0;i<n;i++){ //B만 찾아보기
        for(int j = 0;j<m;j++){
            if(visited[i][j] == false && map[i][j] == 'B'){
                dfs_B(i,j);
                b.push_back(B*B);
                B = 1;
            }
        }
    }
 
 
    //벡터에 있는 값 더하고 출력
    B = 0;
    W = 0;
    for(int i = 0;i<b.size();i++){
        B = B + b[i];
    }
 
    for(int i = 0;i<w.size();i++){
        W = W + w[i];
    }
    cout << W << ' ' << B;
}