문제
한 변의 길이가 2의 n제곱인 정사각형의 흑백이미지가 있다.
이 이미지를 '2의 n제곱 X 2의 n제곱'인 2차원배열(matrix)로 정의한다
흑백은 각각 백=0, 흑=1으로 치환한다
주어진 matrix에서 범위가 큰 부분부터 시작하여, '2의 n제곱 X 2의 n제곱'인 범위 안의 요소를 대상으로 다음을 진행한다
1. 요소가 모두 1이면 1을 리턴
2. 요소가 모두 0이면 0을 리턴
3. 위의 두 조건을 통과하지 못하면 X를 리턴하며, 해당 범위를 1/4로 나눠 각 사분면마다 같은 프로세스를 재귀 진행
재귀적 압축을 통해 String타입으로 리턴한다 (즉, 1 0 X로 이루어진 문자열 반환)
문제 예시
1. 재귀적 압축 : 만약 전체 프로세스를 처리하던 도중, 특정 범위가 특정 조건에 부합할 경우, 그 범위안에서 다시 조건에 따른 프로세스를 진행하고(depth + n), 해당 범위 안에서 프로세스가 끝나면 나와서(depth-1) 다시 순차적으로 프로세스 진행하는 형식
2. 아래 예시
4 * 4에서 X라는 조건에 부합하므로 4 * 4를 쪼개서 진행 (depth + 1)
2 * 2로된 첫번째 사분면에서 다시 X라는 조건에 부합하므로 2 * 2를 쪼개서 진행(depth + 1)
1 * 1로된 첫번째 사분면은 X가 아니므로 쪼개지 않음
...
1 * 1로된 네번째 사분면은 X가 아니므로 쪼개지 않음 (여기서 2 * 2로된 첫번째 사분면 프로세스 끝나므로 depth 올라옴)
2 * 2로된 두번째 사분면은 X가 아니므로 쪼개지 않음
...
1 * 1로된 네번째 사분면은 X가 아니므로 쪼개지 않음
풀이
나의 코드
레퍼런스 코드
'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글
| [Init] Java I/O 기본 방법 (0) | 2022.12.28 |
|---|---|
| [백준] 세준세비 (3) | 2022.12.21 |
| [LIS] 주어진 숫자형 배열의 부분배열 중, 엄격한 오름차순인 가장 긴 부분배열의 최대길이 (0) | 2022.10.10 |
| [orderOfPresentation] N개를 나열하는 경우 중 특정 조합의 순서값 구하기 (1) | 2022.10.08 |
| [LPS] (Longest Prefic which is also Suffix) (0) | 2022.10.06 |