[백준/C++] 1303번: 전쟁 - 전투

문제

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

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

 

코드

#include <iostream>
#include <cmath>
using namespace std;

int N, M;                  // 가로(열), 세로(행)의 크기
char grid[101][101];       // W(흰색) 또는 B(파란색) 군대의 위치를 저장하는 배열
bool visited[101][101];    // 특정 위치의 방문 여부를 저장하는 배열
int w_sum;                 // 'W' 군대의 모든 군집 크기 제곱의 합
int b_sum;                 // 'B' 군대의 모든 군집 크기 제곱의 합

int dx[4] = { 1, -1, 0, 0 }; // 방향 벡터 (상하좌우)
int dy[4] = { 0, 0, -1, 1 };

// 깊이 우선 탐색(DFS) 함수: 연결된 같은 색상의 좌표를 탐색하여 군집 크기를 계산
void dfs(int x, int y, int &cnt, char color) {
    visited[x][y] = true;
    cnt++; // 새로운 좌표 방문 시 군집 크기 증가

    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 (grid[nx][ny] == color && !visited[nx][ny])
            dfs(nx, ny, cnt, color);
    }
}

// 특정 색상('W' 또는 'B')의 군집 크기를 계산하고 결과를 합산
void checkWhiteOrBlue(char color, int x, int y) {
    int cnt = 0;         // 해당 군집의 크기
    int power = 0;       // 해당 군집 크기의 제곱 (군집의 위력)

    dfs(x, y, cnt, color); // 현재 위치에서 DFS 실행
    power = pow(cnt, 2);   // 군집 크기의 제곱 계산
    (color == 'W') ? w_sum += power : b_sum += power; // 색상에 따라 결과 저장
}

int main() {
    cin >> N >> M;

    // 격자 입력 받기
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            cin >> grid[i][j];

    // 모든 격자 탐색
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            if (!visited[i][j]) // 미방문 지점에서 탐색 시작
                checkWhiteOrBlue(grid[i][j], i, j);

    // 결과 출력: 흰색 군대와 파란색 군대의 군집 크기 제곱 합
    cout << w_sum << " " << b_sum;

    return 0;
}

 

풀이

DFS 문제

char 타입의 배열에 원소를 입력받아 각 좌표의 값이 W, B인지에 따라 결과값을 별도로 합산해 출력해야 한다.

 

자세한 풀이는 주석으로 대체합니다.