[JAVA / 자바] 백준(BOJ) 2630번 - 색종이 만들기 (실버 3)

 문제 

아래 <그림 1>과 같이 여러 개의 정사각형 칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수)이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색 종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형 칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

---

 입력 

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형 칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

---

 출력 

첫째 줄에는 잘라진 하얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

---

 

---

 문제 접근 방법 

이 문제는 분할 정복(Divide and Conquer) 문제이다.

 

해당 영역이 모두 같은 숫자가 되면 카운팅 되면서 해당 영역은 더 이상의 분할을 하지 않고 끝나게 되지만, 모두 같은 숫자만 있는 것이 아니라면 해당 영역을 9 분할하여 분할된 각각의 영역에서 다시 같은 숫자만 존재하는지 확인해주어야 한다. 이때, 주의할 점은 영역에 같은 숫자만 존재하지 않아 계속 분할하다가 영역의 크기가 1X1이 된다면 그 한 칸 자체가 하나의 색종이기 때문에 저장된 수를 카운팅 해준다.

 

boolean isEqual()

현재 영역에 저장된 숫자가 모두 같은 숫자인지 판단하여 영역에 저장된 숫자가 동일하면 True 반환, 그렇지 않으면 False를 반환해주는 함수이다.

 

void cut()

변수로 받은 영역이 하나의 색종이가 될 수 있는지 없는지 isEqual 함수로부터 확인받아 하나의 색종이로 판단이 되면 카운팅 해주고, 그렇지 않으면 해당 영역을 다시 4 분할하여 각각의 영역을 cut함수를 재호 출하여 위 과정을 반복해준다. 이때, 영역의 크기가 1이라면 그 자체로 하나의 색종이이기 때문에 해당 영역에 저장된 수를 결괏값에 카운팅 해준다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

분할 정복 문제는 대게 비슷한 유형인 것을 알 수 있다. 최근에 분할 정복 문제를 많이 다뤘는데 모두 거의 동일한 문제였다. 처음엔 분할 정복 문제가 정답률이 높은 이유가 잘 이해되지 않았는데 이렇게 풀어보면 정답률이 높은 이유를 알 것만 같다.

 

 ▼ 이번 문제와 유사한 문제 ▼ 

[JAVA / 자바] 백준(BOJ) 1780번 - 종이의 개수 (실버 3)

[JAVA / 자바] 백준(BOJ) 1992번 - 쿼드 트리 (실버 1)

---

 문제 원본 

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 알고리즘 분류 

 

• 분할 정복
• 재귀​