[C++] 1303 전쟁 - 전투

 

1303번: 전쟁 - 전투

 

BFS 문제로, 간단한 탐색 문제이다. 행과 열을 2차원 배열로 받아 B, W 각각 너비우선탐색 후 모여있는 병사들의 값을 제곱해 더하고 결과를 내주면 된다. 진짜 간단한 문제라 해결책 찾는 건 어렵지 않았는데 자꾸 13%에서 죽어버려서 거의 2시간은 헤맨 거 같다ㅜㅜ

 

결과적으론 문제 제대로 안 읽어서 이렇게 헤맸던 것... 문제를 자세히 보면 가로 길이가 N, 세로 길이가 M. 즉 행이 M 열이 N인데 보통 대부분의 문제들에서 먼저 오는 값이 행, 나중에 오는 값을 열로 입력 받다보니 습관처럼 이렇게 받았다. 하필 예제가 N=M이라 틀린 곳 찾는 데 더 오래걸렸다. (결론 = 문제를 꼼꼼히 읽자..)

 

[해결답안]

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

int N,M; 
char arr[101][101];
int visited[101][101] = {0,};
queue<pair<int,int>> q; //white team
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int blue = 0; int white = 0;


void BFS(char c){
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(!visited[i][j]){
                if(arr[i][j]==c){
                    visited[i][j] = 1;
                    int cnt = 0;
                    q.push(make_pair(i,j));
                    while(!q.empty()){
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        cnt++;
                        for(int k=0; k<4; k++){
                            int mx = x+dx[k]; int my = y+dy[k];
                            if (mx < 0 || mx >= N || my < 0 || my >= M)
							    continue;
                            if(arr[mx][my]==c&&!visited[mx][my]){
                                q.push(make_pair(mx,my));
                                visited[mx][my] = 1;
                            }
                        }
                    }
                    if(c=='W') white += (cnt*cnt);
                    else if(c=='B') blue += (cnt*cnt);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin>>M>>N;

    for(int i=0; i<N; i++){
        string s;
        cin>>s;
        for(int j=0; j<M; j++){
            arr[i][j] = s[j];
        }
    }  
    BFS('W'); 
    BFS('B');
    cout<<white<<" "<<blue;
}