💎 문제
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
💎 입력
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
ex)
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011
💎 출력
영상을 압축한 결과를 출력한다.
ex) ((110(0101))(0010)1(0001))
💎 풀이 방법
문제 자체는 쉬웠는데.... 왜그랬는지 한참 돌아가고 돌아가다가 결국 아이디어를 참고했다....ㅠㅠㅠㅠ저번 Z문제에서 분할정복을 풀었을 때 처럼 '아 끝까지 나누고 난 뒤에 나눌 수 없을 때까지 돌아간 뒤에 합쳐야겠다'라는 생각에만 꽂혀있어서 오히려 복잡하게 접근하고 결국 아이디어를 참고하였다 ㅠㅠ.
분할정복특의 문제처럼 나눠지기 쉽게 N X N 배열에서 2로 계속 나눈 뒤에 그 안에 있는 내용들을 합칠 수 있다면 합치고 그렇지 못하면 그대로 가지고 나오는 방식으로 이해자체는 이지했다. 다만 앞서 말한 것처럼 끝까지 분할한 후에 합쳐야겠다라는 생각보다는 분할정복 문제더라도 어떠한 조건으로일때만 분할시킨 후 굳이 합치지 않고 그대로 출력한다 라는 생각이 빠르게 풀 수 있는 방법인 것 같다. 여기서 그러한 조건은 탐색하는 첫 자리의 값이 나머지 값과 일치하는지 일치하지 않는지 확인하는 것이다.
만약 탐색의 첫 부분이 반복문을 순회하면서 값이 일치하지 않는다면 문제의 조건처럼 4가지 영역으로 나눠서 생각해봐야한다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 순서로 4가지의 영역을 범위의 크기를 반씩 줄여가면서 그 구역의 값들이 일치하는지 안하는지를 확인하면서 출력하는 것이다.
위의 그림과 같은 방식대로 이동하면서 탐색하고 결과를 출력하는 것이다!!
구현하는 함수의 내용은 다음과 같다.
void pressed(int n, int a, int b){
for(int i = a; i < a + n;i++){
for(int j = b;j < b + n;j++){
if(v[a][b] != v[i][j]){
cout << "(";
pressed(n / 2, a, b);
pressed(n / 2, a, b + n / 2);
pressed(n / 2, a + n / 2, b);
pressed(n / 2, a + n /2, b + n / 2);
cout << ")";
return;
}
}
}
cout << v[a][b];
}분할을 하면서 같이 결과를 출력할 수도 있겠다라는 생각을 저번 문제와 겹쳐서 생각하다보니 떠오르지가 않아서 너무 헤맸다....입력받은 문자들을 계속해서 재귀해 나갈 것인데, 이때 String을 줄마다 입력받았기 때문에 이차원배열과 같은 형식으로 절반을 기준으로 하여 구역 4개로 나누고 이 4개의 구역을 재귀해 나갔다. 출력은 만약 4개의 구역을 다시 재귀해서 확인해야 한다면 '()' 괄호기호를 이용해서 감싸주고 만약 for문을 검사한 뒤 함수가 반환되지 않았다면 그 구역의 값들은 모두 똑같을 것이기 때문에 첫 검사자리의 값을 그대로 출력해주는 방식으로 문제를 해결하였다.
💎 전체 코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int N;
string v[65];
void pressed(int n, int a, int b){
for(int i = a; i < a + n;i++){
for(int j = b;j < b + n;j++){
if(v[a][b] != v[i][j]){
cout << "(";
pressed(n / 2, a, b);
pressed(n / 2, a, b + n / 2);
pressed(n / 2, a + n / 2, b);
pressed(n / 2, a + n /2, b + n / 2);
cout << ")";
return;
}
}
}
cout << v[a][b];
}
int main(int argc, const char * argv[]) {
cin >> N;
for(int i = 0;i < N;i++){
cin >> v[i];
}
pressed(N, 0, 0);
cout << "\n";
return 0;
}
💎 고민
진짜 진짜 너무 미련하게 풀다가 결국 지쳐서 아이디어를 확인한 문제인데,,,이번 교훈으로 문제를 딱 마주하다보면 어떤 식으로 풀어야 겠구나의 접근을 해야지 모든 문제가 이전에 풀었던 알고리즘과 같은 방식이 바로 적용되기 쉽구나라는 생각은 버려야겠다. 특히 재귀하는 문제이다보니 간결해지지 않으면 코드가 더 복잡해질 수 있었고 그래서 오히려 재귀를 이용하는 문제는 원리를 이해하고 결과 값을 함께 반환하는 방법은 없을지 라는 생각을 얻게해준 것 같다.
화팅하자...ㅠ
