[백준, 2630번] 색종이 만들기 (분할 정복, 재귀, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 색종이 만들기" 문제는 하얀색(0)과 파란색(1)로 칠해진 종이가 주어지고 전체 종이가 모두 같은색으로 칠해있지 않으면 N/2로 나눠가면서 모든 영역의 종이가 같은색으로만 이루도록 만들고, 각 종이의 색깔의 개수를 출력하는 문제입니다.

---

 

위와 같이 최종적으로 나누어진 색종이들을 보면, 흰색은 9개, 파란색은 7개로 나누어집니다.

---

제가 접근한 방법은 다음과 같습니다.

 

1. 주어진 종이 전체가 하나의 색깔로 이루어져 있는지 확인
   • 모두 같은 색이면 하얀색 종이 개수 또는 파란색 종이 개수를 증가시키고 종료.
2. 하나의 색깔이 아니라면 4등분(재귀 호출)
   • N × N 크기의 종이를 N/2 × N/2 크기의 네 개의 부분으로 나누고,
   • 각각을 재귀적으로 검사.

이 때 4등분으로 나누는 이유는 다음과 같습니다.

영역 안에 서로 다른 색깔이 섞여 있다면, 이 영역을 4개의 작은 정사각형으로 나누어 다시 검사해야 합니다.

위와 같이 하나의 영역을 4가지 영역으로 나누어 각각의 영역을 재귀적으로 검사합니다.

이렇게 나눈 각각의 영역에 대해 다시 같은 과정을 반복하며, 모든 칸이 같은 색이 될 때까지 계속해서 분할하고 검사합니다. 이러한 분할 정복(Divide and Conquer) 방식을 통해 전체 종이를 효율적으로 처리할 수 있기 때문입니다.

 

---

전체 코드

 

문제의 핵심은 영역의 색종이가 모두 같은색이 아니라면, 주어진 요구사항대로 범위를 줄여야한다는 것입니다.

 

이를 위해 재귀적으로 범위를 수정하며 각 영역을 검사합니다.

 

즉, 하나의 큰 정사각형을 4개의 작은 정사각형으로 나누고, 각각의 작은 정사각형에 대해 같은 과정을 반복하는 것입니다. 이러한 과정은 모든 칸이 같은 색이 될 때까지 계속되며, 이는 분할 정복 알고리즘의 전형적인 예시라고 할 수 있습니다. 

 

또한 27번째 줄에서 볼 수 있듯이 각 영역의 첫번째 포인트만 비교하여 색깔의 개수를 카운트합니다. 이는 각 영역이 모두 같은색으로만 이루어져 있다는 것이 확인된 후에 수행되는 작업입니다.

 

즉, isAllSame이 true인 경우에만 해당 영역을 하나의 색종이로 간주하여 카운트하게 됩니다. 이렇게 함으로써 불필요한 중복 검사를 피하고 효율적으로 색종이의 개수를 셀 수 있습니다.