[백준] 1992번 쿼드트리 (JAVA)

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

1992번: 쿼드트리

 

• 문제 이해
• 해결 방법
• 코드 구현

 

---

문제 이해

 

재귀 함수를 이용한 문제들을 많이 풀어보고 있다. 이전에 풀었던 재귀 문제와 해결 사고 과정이 비슷하여 오래 걸리지 않은 것 같다.

이러한 문제들은 분할적으로 재귀 함수를 호출할 때 index를 조정하는 부분만 잘 처리해주면 금방 풀린다.

 

해당 문제가 다른 문제와 달랐던 점은 출력 방법이 달랐다. 일반적으로 별을 그리거나 개수를 세는 문제인데

괄호와 숫자가 조합되어 출력되어 처음엔 이해가 잘 안 갔다. 자세히 보니 검사 부분에 해당 사각형 부분이 0과 1이

같이 있다면 재귀 함수 호출 이전에 "("를 추가해주고 모든 재귀 함수가 종료되어 제어가 돌아올 때 ")"를 추가해주면 되는 것 같았고, 그 방법이 맞았다.

 

 

---

해결 방법

 

재귀 함수의 선언부는 (size, 행, 열) 순서로 만들어서 함수를 작성했다.

처음 재귀 함수를 호출할 때 입력 size 크기와 행 index, 열 index를 보내주면서 size를 간격으로 사용했다.

 

그리고 재귀 함수를 호출하기 이전에 먼저 0 또는 1의 총개수가 size * size의 개수만큼 있는지 확인했다.

만약 개수가 맞다면 이 함수는 0 또는 1로 가득 찬 사각형이 맞으므로 더 이상 재귀 함수를 호출하지 않고

StringBuilder에 해당 숫자를 추가해주며 return으로 종료해주었다.

 

만약 다른 경우로 0과 1의 개수가 size * size의 개수와 맞지 않다면 한 사각 형안에서 0과 1이 같이 있다는 의미이므로

4 부분으로 나누어 재귀 함수를 다시 호출해주어 한다. 재귀 함수를 호출하기 이전에 "("를 StringBuilder에 넣어주고

해당 함수에서 호출한 재귀 함수들이 모두 종료될 때 다시 ")"를 추가해주어야 하므로 for문이 종료되면 추가해주도록 했다.

 

for문 안에서는 재귀 함수를 4 부분으로 호출해주기 위해 시작 위치 index를 시작으로 하고 간격만큼 시작 위치에 더해주며

간격을 2번 곱한 지점까지 닿지는 않도록 반복문 종료 조건을 추가해주어 1행 1열, 1행 2열, 2행 1열, 2행 2열 순서로

재귀 함수를 호출해주도록 했다.

 

모든 재귀 함수가 종료되면 main함수에서 StringBuilder를 출력시켜 정답과 일치하는지 보았다.

 

추가적으로 생각했던 건

0과 1의 개수를 셀 때 boolean type으로 false로 지정해두고, 0이 있다면 true로 만드는 부분과 1이 있다면 true로 만드는 부분 두 개를 구현해놓는다면

0과 1이 모두 true일 때 한 사각 형안에 0과 1이 둘 다 있다는 의미이므로 모든 개수를 세지 않아도 되니 시간 복잡도를 조금 줄일순 있을 것 같았다.

그리고 둘다 true가 아니면 0 또는 1만 있다는 뜻이므로 true인 부분만 StringBuilder에 넣어주면 될 것 같은데,

제출하니 시간 초과가 걸리지 않아서 이 부분은 구현하지 않았다.

시간 초과가 걸리면 재귀 함수의 호출의 개수를 줄일순 없으니 이 부분을 수정했을 것 같다.

 

 

---

코드 구현

 

 

출력 화면