(C++) - 백준(BOJ) 1303번 : 전쟁 - 전투

www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

bfs기본 문제였습니다.

 

풀이방법

 1. 설계 : W병사의 영역, B병사의 영역을 구해 각자 더한 후 출력합니다.

 2. bfs실행 : queue를 시용합니다. 방문하지 않은 곳이 만약 같은 병사가 위치한 곳이라면 방문한 뒤 해당 병사의 명 수를 ++해줍니다. 그 후 그 부분을 다시방문해 다음 병사를 살펴봐야 하므로 해당 위치를 push 해줍니다. 영역의 크기를 다 셌다면 영역 넓이 * 영역 넓이 를 반환합니다. 이는 처음 bfs가 호출될 때 인자로 현재 위치 i,j를 인자로 넘겨주는데 이로써 더해줄 영역이 'W'인지 'B'인지 알 수 있습니다.

 3. 정답 출력

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char board[101][101];
int visited[101][101];
int bPower,wPower,n,m;
int bfs(int i, int j){
    int cnt = 1;
    char c = board[i][j];
    queue <pii> q;
    q.push({i,j});
    visited[i][j] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0 ; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= m || 0 > ny || ny >= n) continue;
            if(visited[nx][ny] || board[nx][ny]!=c) continue;
            visited[nx][ny] = 1;
            cnt++;
            q.push({nx,ny});
        }
    }
    return cnt * cnt;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++)
        cin >> board[i];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(!visited[i][j]){
                if(board[i][j] == 'W') wPower += bfs(i,j);
                else bPower += bfs(i,j);
            }
        }
    }
    cout << wPower << ' ' << bPower <<'\n';
}