[백준] 1303번. 전쟁 - 전투

[백준] 1303번. 전쟁 - 전투

1. 문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

2. 입력

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

3. 출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

4. 풀이

• BFS 뭉쳐있는 사람 수를 구하고 사람 수^2를 리턴하는 함수를 만들었다.
• 배열을 돌면서 방문하지 않은 노드를 BFS를 하며 전투력을 누적시켰다.

5. 처음 코드와 달라진 점

• n과 m을 반대로 적어서 수정했다.
  n과 m을 동시에 바꾸는데 n을 m으로 바로 바꾸면 m을 n으로 바꿀 수 없어서 n을 asdf로 먼저 바꿨다. 별거 아닌데 괜히 뿌듯하다...ㅎ
• BFS를 하는 동안 적을 찾을 지 아군을 찾을 지 처음에 함수의 매개변수로 전달했는다. 생각해보니 인덱스가 있으니 함수 처음 시작할 때 map에서 찾도록 수정했다.

6. 코드

#include <iostream>
#include <queue>

using namespace std;

char map[100][100];
bool visited[100][100];
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int m, n;

int bfs(int start_x, int start_y) {
    int number_of_people = 1;
    char side = map[start_x][start_y];
    visited[start_x][start_y] = true;
    queue<pair<int, int>> q;
    q.push({ start_x, start_y });

    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 (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (visited[nx][ny] || map[nx][ny] != side) continue;
            
            visited[nx][ny] = true;
            number_of_people++;
            q.push({ nx, ny });
        }
    }
    return number_of_people * number_of_people;
}

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
   
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
        
    int power_of_ally = 0, power_of_enemy = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && map[i][j] == 'W') power_of_ally += bfs(i, j);
            else if (!visited[i][j] && map[i][j] == 'B') power_of_enemy += bfs(i, j);
        }
    }
    cout << power_of_ally << " " << power_of_enemy;
}