백준 1303: 전쟁 - 전투(c++, 구현 & 그래프탐색 & BFS)

사용 언어	티어	시간 제한	메모리 제한
c++		1초	128MB

 

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

1303번: 전쟁 - 전투

 

#0 문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

 

#1 입력

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

 

#2 접근

• 전형적인 그래프 탐색 문제이다. 많이 접해봤던 문제라면 10분 정도면 쉽게 해결할 난이도의 문제이다.
• n, m이 각각 가로, 세로임에 유의한다.

 

#3 풀이

• BFS로 그래프 탐색을 한다.
• 미리 나와 적의 좌표를 벡터에 각각 저장해둔다. 이후에 BFS를 여러 번 돌릴 때 간단하게 처리하기 위함이다.
• BFS로 탐색하면서 연결된 요소들의 개수를 세고 제곱한 것을 리턴하도록 한다.
• 합을 각각 계산해서 출력하면 된다.

 

#4 코드

/*
1303 전쟁 - 전투
구현, 그래프탐색
*/

#include <iostream>
#include <string>
#include <queue>
#include <vector>




using namespace std;

typedef pair<int, int> P;


int n, m;

int board[101][101];
bool visited[101][101];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};


int bfs(int row, int col, int team) {
    int cnt = 0;
    queue<P> q;

    visited[row][col] = true;
    q.push({row, col});

    while (!q.empty()) {
        P node = q.front();
        q.pop();
        cnt++;

        int x = node.first;
        int y = node.second;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (!visited[nx][ny] && board[nx][ny] == team) {
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    return cnt * cnt;
}




int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string line;
    cin >> n >> m;

    vector<P> me;
    vector<P> enemy;

    for (int i = 0; i < m; ++i) {
        cin >> line;
        for (int j = 0; j < n; ++j) {
            if (line[j] == 'W') {
                board[i][j] = 1;
                me.push_back({i, j});
            } else enemy.push_back({i, j});
        }
    }

    int my_score = 0;
    for (P w : me) {
        int row = w.first;
        int col = w.second;
        if (!visited[row][col]) my_score += bfs(row, col, 1);
    }


    int enemy_score = 0;
    for (P b : enemy) {
        int row = b.first;
        int col = b.second;

        if (!visited[row][col]) enemy_score += bfs(row, col, 0);
    }

    cout << my_score << " " << enemy_score;

    return 0;
}