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

 문제 

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

---

 입력 

첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

---

 출력 

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

---

 

---

 문제 접근 방법 

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

 

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

 

boolean isEqual()

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

 

void cutting()

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

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

분할 정복 문제 치고 패턴이 단순해서 로직을 생각하는데 크게 오래 걸리지는 않았다. 그래도 다른 문제에 비해 분할 정복 문제를 푸는 시간이 보다 오래 걸리는 감이 없지 않아 있다. 좀 더 노력해야겠다.

 

 

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

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

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

---

 문제 원본 

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

1780번: 종이의 개수

 알고리즘 분류 

• 분할 정복
• 재귀