[BaekJoon 1303번] 전쟁 - 전투(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1303번: 전쟁 - 전투

 

 

[문제 설명]

 

 

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

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

 

 

[입력]

 

 

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
5 5 WBWWW WWWWW BBBBB BBBWW WWWWW	130 65

 

 

[문제 풀이]

 

쉬운 문제인데, 처음에 풀었을 때 세그먼트 에러가 발생했다. 이유는 아직 잘 모르겠다.(꒦ິㅁ꒦ິ)

일단은 의심은 가는 곳이 있어서 다시 풀어보기로 했다.

 

처음 코드를 작성했을 땐 전쟁터의 입력을 받을 때 띄어쓰기 없이 입력이 되기 때문에 string 으로 받아서 전쟁터 지도를 만들었다.

맞은 코드는 전쟁터의 입력을 받을 때 char형으로 입력을 받고

해당 문자가 'W'이면 전쟁터 지도 각 좌표를 1로 저장, 'B'이면 전쟁터 지도 각 좌표를 0으로 저장하도록 했다.

 

그리고 처음 작성했던/맞은 코드 모두 아군에 대한 BFS, 적군에 대한 BFS를 사용해서 각 위렵의 합을 구했다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

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

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int board[101][101];
bool q1visited[101][101];
bool q2visited[101][101];

int main(void) {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            char c;
            cin >> c;
            if (c == 'W') board[i][j] = 1; // 아군 1로 표시
            else board[i][j] = 0; // 적군 0으로 표시
        }
    }

    // 아군 BFS
    queue<pair<int, int>> q1;
    int q1sum = 0;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (q1visited[i][j] || board[i][j] == 0) continue;
            int ans = 0;
            q1.push({ i,j });
            q1visited[i][j] = true;
            while (!q1.empty()) {
                pair<int, int> cur = q1.front();
                q1.pop();
                ans += 1;
                for (int k = 0; k < 4; ++k) {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                    if ((q1visited[nx][ny] == true) || (board[nx][ny] == 0)) continue;
                    q1.push({ nx, ny });
                    q1visited[nx][ny] = true;
                }
            }
            q1sum += (ans * ans);
        }
    }

    // 적군 BFS
    queue<pair<int, int>> q2;
    int q2sum = 0;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (q2visited[i][j] || board[i][j] == 1) continue;
            int ans = 0;
            q2.push({ i,j });
            q2visited[i][j] = true;
            while (!q2.empty()) {
                pair<int, int> cur = q2.front();
                q2.pop();
                ans += 1;
                for (int k = 0; k < 4; ++k) {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                    if ((q2visited[nx][ny] == true) || (board[nx][ny] == 1)) continue;
                    q2.push({ nx, ny });
                    q2visited[nx][ny] = true;
                }
            }
            q2sum += (ans * ans);
        }
    }
    cout << q1sum << ' ' << q2sum;
}