[DFS, 난이도 중] 프로그래머즈, 쿼드압축 후 개수 세기
전체 영역을 4분할 한뒤 분할 영역 안의 요소가 모두 같을 경우에는 압축하고, 그렇지 않을 경우에는 분할 영역을 다시 4분할해가는 식으로 진행한다. 이 방식으로 모두 압축했을 때 남아있는 0,1의 개수를 계산하면 되는 문제이다. 자세한 설명은 맨 아래 첨부한 코드의 주석에 달아놓았다. dfs함수를 수행하기 전에 전체 영역에 대해 요소가 모두 같은지 여부를 알아내야 한다. 그 이유는 dfs함수에서는 영역을 4분할 하고 계산하기 때문에, 전체 영역을 바로 넣어버리면 전체 영역에 대해 요소가 모두 같더라도 강제로 4분할이 되어 버린다. 이러한 과정이 없다면, [[1,1],[1,1]] 이 입력으로 주어지더라도 출력값은 [0,1]이 아닌 [0,4]가 되어버릴 것이다. 테스트 케이스 16개 모두 통과 #includ..
2020. 10. 19.
