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

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

1303번: 전쟁 - 전투

문제분석

1. 분류
   • BFS
2. 문제설명
   • 아군은 B, 적군은 W
   • 가로-세로-위-아래 N명이 뭉쳐있으면 Power += N^2
   • 섬 크기 구하기 문제 유형과 비슷한 문제

코드

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

using namespace std;

int axisY, axisX;
vector<string> map;

struct node {
    int y;
    int x;
};
queue<node> q;

int dt[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int Wsum, Bsum;

void bfs(int yy, int xx, char tar) {
    /*
     * 인접해 있는 팀을 발견할 때 마다 cnt++
     * 탐색이 완료된 팀은 'X'표식을 해서 다시 탐색하지 않게 설정
     */
    
    //초기 상태에 대한 정보 입력
    int cnt = 0;
    q.push({yy, xx});
    map[yy][xx] = 'X';
    cnt++;
    
    //bfs 탐색
    node now;
    while (!q.empty()) {
        now = q.front();
        q.pop();

        for (int t = 0; t < 4; t++) {
            int dy = now.y + dt[t][0];
            int dx = now.x + dt[t][1];

            if (dy < 0 || dx < 0 || dy >= axisY || dx >= axisX)continue;
            if (map[dy][dx] != tar) continue;

            cnt++;
            map[dy][dx] = 'X';
            q.push({dy, dx});
        }
    }

    //팀의 힘은 주어진 조건에 따라 제곱해준다.
    if (tar == 'W') Wsum += (cnt * cnt);
    else Bsum += (cnt * cnt);
}

int main() {
    //전쟁터의 크기 입력 (X축, Y축 순으로)
    cin >> axisX >> axisY;
    map.assign(axisY, "");
    
    //전쟁터에 아군 적군 입력
    for (int x = 0; x < axisY; x++) {
        cin >> map[x];
    }

    //전쟁터에 아군 적군 탐색 후 bfs
    for (int y = 0; y < axisY; y++) {
        for (int x = 0; x < axisX; x++) {
            if (map[y][x] == 'W') bfs(y, x, 'W');
            if (map[y][x] == 'B') bfs(y, x, 'B');
        }
    }

    cout << Wsum << " " << Bsum;

    return 0;
}

 

문제풀이

1. 설계
   1. <인접해 있는 섬을 구하기>라는 유형의 탐색 문제와 유사한 것을 알 수 있다.
   2. 조건에 부합하는 팀을 섬이라고 생각하고, 나머지는 바다라고 생각한다.
   3. 인접해 있는 섬을 탐색하고, 탐색할 때 마다 cnt++ 한다.
   4. 탐색이 완료된 섬은 침몰 시키거나 (map[dy][dx]=1 -> map[dy][dx]=0),
   5. 방문 배열을 만들어 방문했음을 표시한다. (visited[dy][dx]=0 -> visited[dy][dx]=1)
   6. 탐색이 완료된 섬의 크기의 제곱이 해당 섬의 크기이다.
2. 주의할 점
   1. 섬의 크기를 구할 때는 탐색 level을 구하는 것이 아니다. cnt++ 해야 한다.
   2. 입력 조건에 가로축, 세로축으로 되어있으니, X축 입력-Y축 입력을 해야 한다.
   3. bfs를 두번 돌리는 것이 아니라, w팀이면, w를 매개변수로 넘겨주어 푸는 것이 효율적이다. [1개의 bfs가 2가지 일을 할 수 있게]