(매일 BOJ) C++ 1303번 전쟁 - 전투

이번 문제는 전쟁 - 전투다

문제 설명

N × M 크기의 전쟁터가 있다
각 칸에는 아군(W) 또는 적군(B)이 배치되어 있고,
같은 진영이 상하좌우로 붙어 있으면 하나의 부대로 취급한

• 부대 전투력 = (부대 인원 수)^2
• 아군과 적군의 총 전투력을 각각 계산

접근 방법

1. 문제 구조 분석

• 입력에서 N(가로, 열), M(세로, 행)이 주어진다
• 전쟁터를 M행 × N열의 2차원 배열로 저장
• 각 칸에서 DFS를 사용하여 같은 진영의 연결된 모든 칸 탐색.
• 방문할 때마다 인원 수(count_parts)를 1씩 증가.
• 탐색이 끝나면 (count_parts)^2를 해당 진영의 전투력에 더함.

2. DFS 탐색

• 상하좌우 이동을 위해 fourway_x와 fourway_y 방향 배열 사용.
• 방문한 칸은 visited 배열에 체크.
• 경계 체크 시 0 ≤ x < M, 0 ≤ y < N을 반드시 지켜야 함.

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS(vector<vector<char>> &field, vector<vector<bool>> &visited,
         int &count_parts, int x, int y, char team);
int fourway_x[4] = {1, -1, 0, 0};
int fourway_y[4] = {0, 0, 1, -1};
int N, M; // N=열(가로), M=행(세로)

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M; // N=열, M=행
    vector<vector<char>> field(M, vector<char>(N));

    for (int i = 0; i < M; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < N; j++) {
            field[i][j] = str[j];
        }
    }

    vector<vector<bool>> visited(M, vector<bool>(N, false));
    int sum_w = 0, sum_b = 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j]) {
                int count_parts = 0;
                DFS(field, visited, count_parts, i, j, field[i][j]);
                if (field[i][j] == 'W') sum_w += count_parts * count_parts;
                else sum_b += count_parts * count_parts;
            }
        }
    }

    cout << sum_w << ' ' << sum_b << '\n';
}

void DFS(vector<vector<char>> &field, vector<vector<bool>> &visited,
         int &count_parts, int x, int y, char team) {
    visited[x][y] = true;
    count_parts++;

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

        if (nx >= 0 && ny >= 0 && nx < M && ny < N &&
            !visited[nx][ny] && field[nx][ny] == team) {
            DFS(field, visited, count_parts, nx, ny, team);
        }
    }
}