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

문제

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

 

문제 이해

N × M 전쟁터에서 우리 병사(W)의 위력의 합과 적국의 병사(B)의 위력의 합을 구한다.

N명이 뭉쳐있을 때 N²의 위력을 낼 수 있다.

 

문제 풀이

💡 DFS & BFS

• 첫 번째 칸부터 dr, dc 배열을 이용해서 같은 문자('W' / 'B')가 있는 곳을 상하좌우로 탐색한다.
  이미 방문한 곳은 탐색하지 않는다.
• 탐색하는 곳은 방문 표기하고, 해당 병사 수 카운트를 증가시킨다.
• 탐색을 종료한 후 뭉쳐있는 병사의 위력을 저장한다.
• 병사의 위력을 합한 값을 각각 출력한다.

 

코드

1️⃣ DFS

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int n, m, cnt;
char color;
vector<vector<char>> board;
vector<vector<bool>> visited;
vector<int> w, b;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void dfs(int r, int c)
{
    // 인덱스
    // 종료 조건: 같은 병사가 아니거나 이미 방문한 곳
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != color || visited[r][c])
        return;
    
    cnt++;
    visited[r][c] = true;
    
    for (int i = 0; i < 4; i++)
        dfs(r + dr[i], c + dc[i]);
}

int main()
{
    // 입력
    cin >> n >> m;
    board.assign(m, vector<char>(n));
    visited.assign(m, vector<bool>(n, false));
    for (int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }

    // 연산
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                color = board[i][j];
                cnt = 0;
                dfs(i, j);
                if (color == 'W')
                    w.push_back(cnt * cnt);
                else
                    b.push_back(cnt * cnt);
            }
        }
    }
    
    // 출력
    cout << accumulate(w.begin(), w.end(), 0) << ' ' << accumulate(b.begin(), b.end(), 0);

    return 0;
}

 

2️⃣ BFS

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>

using namespace std;
typedef pair<int, int> pii;

int n, m, cnt;
char color;
vector<vector<char> > board;
vector<vector<bool> > visited;
vector<int> w, b;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void bfs(int r, int c) {
    queue<pii> q;

    q.push(make_pair(r, c));
    visited[r][c] = true;

    while (!q.empty()) {
        auto [r, c] = q.front();
        cnt++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || board[nr][nc] != color || visited[nr][nc])
                continue;
            q.push(make_pair(r + dr[i], c + dc[i]));
            visited[nr][nc] = true;
        }
    }
}

int main() {
    // 입력
    cin >> n >> m;
    board.assign(m, vector<char>(n));
    visited.assign(m, vector<bool>(n, false));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }

    // 연산
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                color = board[i][j];
                cnt = 0;
                bfs(i, j);
                if (color == 'W')
                    w.push_back(cnt * cnt);
                else
                    b.push_back(cnt * cnt);
            }
        }
    }

    // 출력
    cout << accumulate(w.begin(), w.end(), 0) << ' ' << accumulate(b.begin(), b.end(), 0);

    return 0;
}