https://www.acmicpc.net/problem/2630
문제 해결 과정
착안
분할 정복(divide and conquer) 알고리즘을 통해 정사각형 모양의 색종이가 균일한 색깔을 가지는지 확인하고, 균일한 색으로 이루어져 있지 않다면 동일한 크기의 4 개의 작은 색종이로 나누어가며 색종이 내부의 색깔이 일정한지 확인하는 과정을 반복하여 해결하고자 하였다.
구현
배열의 인덱스를 좌표와 같이 사용하여 색종이의 좌상단 좌표와 한 변의 길이를 매개변수로 구간을 나누는 함수를 구현하고, 나누어진 색종이들의 색이 일정한지 확인하는 함수를 구현하였다. 색이 일정하지 않은 경우는 재귀적으로 다시 색종이를 1/4의 크기로 나누어 반복 확인하도록 구현하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
using namespace std;
int N;
int Paper[128][128];
int White;
int Blue;
bool IsHomogeneous(int x, int y, int len)
{
for (int i = y; i < y + len; i++)
for (int j = x; j < x + len; j++)
if (Paper[y][x] != Paper[i][j])
return false;
return true;
}
void Partition(int x, int y, int len)
{
int half = len / 2;
if (IsHomogeneous(x, y, len))
{
if (Paper[y][x])
Blue++;
else
White++;
}
else
{
Partition(x, y, half);
Partition(x + half, y, half);
Partition(x, y + half, half);
Partition(x + half, y + half, half);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> Paper[i][j];
Partition(0, 0, N);
cout << White << "\n" << Blue << "\n";
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 4134번: 다음 소수 (0) | 2023.07.02 |
---|---|
[Baekjoon] 14889번: 스타트와 링크 (0) | 2023.07.02 |
[Baekjoon] 2805번: 나무 자르기 (0) | 2023.06.27 |
[Baekjoon] 1654번: 랜선 자르기 (0) | 2023.06.27 |
[Baekjoon] 10814번: 나이순 정렬 (0) | 2023.06.25 |
댓글