출처 : https://www.acmicpc.net/problem/1303
문제
전쟁터에서 W팀과 B팀이 싸우고 있다. 각각의 병사들이 같은 팀 병사들과 연결되어 있을 때, 병사의 수의 제곱만큼 전투력이 생긴다. 전장의 병사 정보를 받아 각각 팀의 전투력을 구하는 문제이다.
생각
- bfs로 풀자 (dfs로도 풀는거 연습해야 하는데)
- 각 그룹만큼 크기를 구한 후에 전투력 총합에 제곱으로 더하자
- 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 암시적 변환
- 제발 문제좀 제대로 봐라
'코딩테스트' 카테고리의 다른 글
백준 2206 : 벽 부수고 이동하기 (0) | 2025.05.09 |
---|---|
백준 9019 : DSLR (0) | 2025.05.07 |
백준 10026 : 적록색약 (0) | 2025.05.03 |
백준 2644 : 촌수계산 (0) | 2025.03.09 |
백준 1793: 타일링 (0) | 2025.03.07 |