문제

문제링크

해설

• 두 가지를 조심하면 되는 문제입니다.
  1. 분할할 필요가 없는 경우 괄호 ‘()’를 삽입하지 않습니다.
  2. 더 이상 분할할 수 없는 경우에 대한 예외처리를 반드시 고려해야 합니다.
• 우선, 분할할 필요가 있는지 없는지 여부를 검사해야 합니다. 범위 내에 단 하나라도 다른 요소가 있다면, 분할이 필요하고, 모두 같다면 분할할 필요가 없습니다.
• 분할해야 한다면, 4분할한 뒤 각 시작점마다 재귀함수를 호출합니다.

• 위 함수를 예로 들면, 현재 위치 (sy, sx)를 기준으로 4분할한 각 시작점은 아래와 같습니다.
  • (sy, sx)
  • (sy, nx) == (sy, sx + length / 2)
  • (ny, sx) == (sy + length / 2, sx)
  • (ny, nx) == (sy + length / 2, sx + length / 2)
• 더 이상 분할할 수 없는 경우, 제 코드의 is_compress_needed() 함수에서 false를 반환하므로 따로 예외처리를 할 필요는 없었습니다.

코드

#include <iostream>
#include <vector>
using namespace std;

vector<string> img;

bool is_compress_needed(int length, int sy, int sx) {
    for (int y = sy; y < sy + length; y++)
        for (int x = sx; x < sx + length; x++)
            if (img[y][x] != img[sy][sx]) return true;
    return false;
}

string compress(int length, int sy, int sx) {
    int next_length = length / 2;
    int ny = sy + next_length, nx = sx + next_length;

    string ret = "(";
    // 좌측 상단 (1)
    if (!is_compress_needed(next_length, sy, sx)) ret += img[sy][sx];
    else ret += compress(next_length, sy, sx);

    // 우측 상단 (2)
    if (!is_compress_needed(next_length, sy, nx)) ret += img[sy][nx];
    else ret += compress(next_length, sy, nx);

    // 좌측 하단 (3)
    if (!is_compress_needed(next_length, ny, sx)) ret += img[ny][sx];
    else ret += compress(next_length, ny, sx);

    // 우측 하단 (4)
    if (!is_compress_needed(next_length, ny, nx)) ret += img[ny][nx];
    else ret += compress(next_length, ny, nx);

    return ret + ")";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int N;
    cin >> N;

    img.resize(N);
    for (int i = 0; i < N; i++) cin >> img[i];

    if (!is_compress_needed(N, 0, 0)) cout << img[0][0] << '\n';
    else cout << compress(N, 0, 0) << '\n';

    return 0;
}

소스코드 링크

결과