[C++] 백준 1992번 쿼드트리

분할 정복 / 재귀 문제

예전에 이 문제를 풀려고 고민을 많이 해봤는데 도저히 모르겠어서 검색해봤는데,

분할 정복 알고리즘을 재귀로 구현해서 푸는 문제였다.

오늘 분할 정복 알고리즘을 정리해서 풀었더니 쉽게 풀 수 있었다. 정답 비율이 높은 이유가 있었다.

 

문제풀이

예전에 색종이 만들기 문제와 비슷하다.

다만 이 문제같은 경우에는 자를 때 해당 색이 무엇이고, 출력을 어떻게 해야하는지가 추가된 문제이다.

사용한 STL과 변수

가로, 세로의 길이를 입력받는 widthHeight와 판의 정보를 입력받는 board 배열이 있다.

 

분할 정복 메서드

먼저, 현재 좌표의 숫자를 받는다. 그 후 해당 색종이의 모든 색이 같은지 확인하는 same 변수를 만든다.

만일 이중 for문에서 다른 색이 있으면 same 변수를 false로 만들어 준다.

 

다른색이 있으면 4등분하게 되는데, 4등분 하기 전에 '('를 출력하고 4등분이 끝나면 ')'를 출력하게 만든다.

4등분하는 경우는 size가 1이될 경우, 자기 자신만 확인하게 되므로 무조건 출력하게 된다.

그리고 다른 색이 없다면 그냥 그 숫자를 출력하게 한다.

 

메인함수

가로, 세로의 길이를 입력받은 후에 입력이 모두 붙어있는 상태로 주어지므로, 문자열로 입력받아서 각 칸을

개별적으로 입력하게 하는식으로 만들었다.

후에 분할 정복 메서드를 실행시키면 된다.

 

분할 정복 알고리즘을 알고있다면 쉽게 해결할 수 있는 문제였다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 여기서 확인이 가능하다.