백준 1303 : 전쟁

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

 

---

문제

전쟁터에서 W팀과 B팀이 싸우고 있다. 각각의 병사들이 같은 팀 병사들과 연결되어 있을 때, 병사의 수의 제곱만큼 전투력이 생긴다. 전장의 병사 정보를 받아 각각 팀의 전투력을 구하는 문제이다.

---

생각

1. bfs로 풀자 (dfs로도 풀는거 연습해야 하는데)
2. 각 그룹만큼 크기를 구한 후에 전투력 총합에 제곱으로 더하자
3. bfs가 한번 끝나는 지점에서 점수를 더하면 된다

---

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

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

int main()
{
    int n;
    cin >> n;

    vector<string> field;

    for(int ix = 0; ix < n; ++ix)
    {
        string line;
        cin >> line;
        field.emplace_back(line);
    }

    int sum_W = 0;
    int sum_B = 0;
    
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<pair<int, int>> q;
    for(int ix = 0; ix < n; ++ix)
    {
        for(int jx = 0; jx < n; ++jx)
        {
            int count_W = 0;
            int count_B = 0;

            if(!visited[ix][jx])
            {
                q.push({ix, jx});
                visited[ix][jx] = true;
                while(!q.empty())
                {
                    auto [cur_x, cur_y] = q.front();
                    q.pop();

                    if(field[cur_x][cur_y] == 'W')
                    {
                        ++count_W;
                    }
                    else if(field[cur_x][cur_y] == 'B')
                    {
                        ++count_B;
                    }

                    for(int kx = 0; kx < 4; ++kx)
                    {
                        int nex_x = cur_x + dx[kx];
                        int nex_y = cur_y + dy[kx];

                        if(nex_x >= 0 && nex_x < n && nex_y >= 0 && nex_y < n)
                        {
                            if(!visited[nex_x][nex_y])
                            {
                                if(field[cur_x][cur_y] == field[nex_x][nex_y])
                                {
                                    q.push({nex_x, nex_y});
                                    visited[nex_x][nex_y] = true;
                                }
                            }
                        }
                    }
                }
                cout << count_W << " " << count_B << "\n";
                cout << ix << " " << jx << "\n";
                sum_W += pow(count_W, 2);
                sum_B += pow(count_B, 2);
            }
        }
    }

    cout << sum_W << " " << sum_B;

}

---

틀린 이유

• 입력값이 n, m 인데 입력을 n만 해서 문제가 됨
• n, m 위치 다르게 작성해서 틀림 -> 슬슬 걱정된다

---

수정 코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

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

int main()
{
    int n, m;
    cin >> n >> m;

    vector<string> field;

    for(int ix = 0; ix < m; ++ix)
    {
        string line;
        cin >> line;
        field.emplace_back(line);
    }

    int sum_W = 0;
    int sum_B = 0;
    
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<pair<int, int>> q;

    for(int ix = 0; ix < m; ++ix)
    {
        for(int jx = 0; jx < n; ++jx)
        {
            int count_W = 0;
            int count_B = 0;

            if(!visited[ix][jx])
            {
                q.push({ix, jx});
                visited[ix][jx] = true;
                while(!q.empty())
                {
                    auto [cur_x, cur_y] = q.front();
                    q.pop();

                    if(field[cur_x][cur_y] == 'W')
                    {
                        ++count_W;
                    }
                    else if(field[cur_x][cur_y] == 'B')
                    {
                        ++count_B;
                    }

                    for(int kx = 0; kx < 4; ++kx)
                    {
                        int nex_x = cur_x + dx[kx];
                        int nex_y = cur_y + dy[kx];

                        if(nex_x >= 0 && nex_x < m && nex_y >= 0 && nex_y < n)
                        {
                            if(!visited[nex_x][nex_y])
                            {
                                if(field[cur_x][cur_y] == field[nex_x][nex_y])
                                {
                                    q.push({nex_x, nex_y});
                                    visited[nex_x][nex_y] = true;
                                }
                            }
                        }
                    }
                }
                sum_W += count_W * count_W;
                sum_B += count_B * count_B;
            }
        }
    }

    cout << sum_W << " " << sum_B;

}

 

---

결과

• 문제 풀이 시간 : 38분
• 메모리 :  2028KB
• 시간 :  0ms

배운점 및 고칠점

• 제곱은 pow 보다 그냥 하는게 더 성능이 좋다
  
  • int -> double 암시적 변환
• 제발 문제좀 제대로 봐라