[ 백준 1303 ] 전쟁 - 전투 (C++)

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

1303번: 전쟁 - 전투

 

BFS로 해결할 수 있는 문제다. 이차원 문자 배열을 map이라고 했을 때 문자값이 'W'인지 'B'인지에 따라 케이스를 나눠 탐색을 진행하야 한다. 나는 type 변수를 두어 1일 때 'W'를, 2일 때 'B'를 탐색하도록 코드를 짰다.

 

방법은 간단하다. 각 군집 벡터 w, b를 생성한 뒤에 map을 처음부터 끝까지 탐색하면서 'W'면 문자에 맞는 군집을 찾아주고 w에 push, 'B'면 문자에 맞는 군집을 찾아주고 b에 push하면 된다. 이때, 재탐색을 막기 위해 visit 배열을 사용한다. 

 

움직일 수 있는 경우의 수는 동서남북 네 가지다. 이는 두 정수를 원소로 가지는 move 벡터를 만들어 구현했다. BFS의 조건문은 아래와 같다. 

 

1. 범위 안에 있고 아직 방문 안 했으면
2. type 문자와 일치하면 방문처리하고 push

큐에 push 해줄 때마다 군집 내 병사 수를 나타내는 cnt 변수에 1을 더해준다.

 

bfs를 돌리고 각 군집 벡터의 원소 제곱합을 출력하기만 하면 된다. 

 

N이 가로, M이 세로임에 주의하자. 이거 때문에 10분 정도 날렸다. 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

char map[100][100];
int visit[100][100];
int N, M;

// type 1: W
// type 2: B

int check(int row, int col, int type){
    vector<pair<int,int>> move = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    queue<pair<int, int>> q;
    int cnt = 1;
    
    visit[row][col] = 1;
    q.push({row, col});
    
    while(!q.empty()){
        row = q.front().first;
        col = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int m_row = row + move[i].first;
            int m_col = col + move[i].second;
            
            // 범위 안에 있고 아직 방문 안 했으면 push
            if(m_row >= 0 && m_col >= 0 && m_row < 100 && m_col < 100){
                if(!visit[m_row][m_col] && type == 1){
                    if(map[m_row][m_col] == 'W'){
                    visit[m_row][m_col] = 1;
                    cnt++;
                    q.push({m_row, m_col});
                    }
                }
                if(!visit[m_row][m_col] && type == 2){
                    if(map[m_row][m_col] == 'B'){
                    visit[m_row][m_col] = 1;
                    cnt++;
                    q.push({m_row, m_col});
                    }
                }
            }
        }
    }
    return cnt;
}

int get_sum(vector<int>& v){
    int sum = 0;
    for(int elem : v)
        sum += (elem * elem);
    return sum;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            cin >> map[i][j];
    
    vector<int> w;
    vector<int> b;
    
    for(int row = 0; row < M; row++){
        for(int col = 0; col < N; col++){
            if(!visit[row][col]){
                if(map[row][col] == 'W')
                    w.push_back(check(row, col, 1));
                else
                    b.push_back(check(row, col, 2));
            }
        }
    }
    
    cout << get_sum(w) << ' ' << get_sum(b) << endl;
    
    return 0;
}