Alphabet Cake

문제파악

이 문제는 한 케이크를 R행 C열로 나누어 아이의 이니셜을 그려주어 해당 이니셜을 가진 사각형 영역의 케익 조각을 아이에게 나눠주려는 문제입니다. 입력으로는 대문자인 이니셜과 아직 그려지지 않았음을 표현하는 ?로 케이크를 2차원 배열로 표현하여 주어집니다. 아이들에게 나눠주기 위해서 자기 이니셜만을 포함하는 사각형을 이뤄야 합니다. 모든 케이크를 분배해야만 하며 동등하게 분배될 필요는 없습니다. 문제에서 주어진 입력에 따른 결과는 수 없이 많을 수 있지만 이 중 하나만 만들면 됩니다.

IDEA

1. 우선 주어진 케익을 잘 나누면 하나의 큰 문제에서 작은 두개의 문제로 나누어서 해결할 수 있다는 점을 깨닫는게 중요합니다.

   예시로, 주어진 입력의 첫번째 케이스를 보면 3X3 케이크를 채우는 문제를 각 행을 나누어 1X3인 케익 3개를 채우는 문제로 해결할 수 있습니다.

2. 잘 나눈다는 것에는 2가지 조건을 포함시킬 수 있습니다.

   1. 나눌 때 가로 또는 세로로 단 한 번만 영역을 나누어 결과물 2개가 모두 사각형을 이루도록 합니다.

   2. 영역을 나눌 기준을 잡습니다

      좌측 최상단에 존재하는 이니셜을 기준으로 잡았습니다.

3. 기준 이니셜보다 하단에 이니셜이 존재한다면 기준 이니셜의 row 값으로 가로로 영역을 나누고 하단에 존재하지 않고 우측에 존재한다면 col 값으로 세로로 영역을 나눕니다.

4. 영역 내 단일 이니셜만 존재할 때 까지 나누기를 수행하며 최종적으로 나눠진 영역에 존재하는 이니셜로 채우고 나눠진 영역을 합치며 결과를 낼수 있습니다.

위와 같은 방식으로 문제를 해결하기 위해서는 좌측 최상단을 영역 나누기할 때 마다 찾아야 합니다. 이를 위해서 초기 케이크 상태에서 모든 이니셜의 좌표값과 문자값을 정렬된 상태로 만들고 이 배열의 인덱싱을 하는 것으로 최상단을 유지 및 영역내 존재하는 이니셜들을 유지하였습니다.

CODE

/*
* map : cake 상태
* nodes : cake내 이니셜의 좌표값과 문자값을 유지하는 배열
*/

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXRC 30

typedef struct node{
    int r,c;
    char val;
} node;

int R, C;
char map[MAXRC][MAXRC];
vector<node> nodes;

/*
* start, end : nodes 배열의 인덱스를 가르킨다. 해당 영역 내 존재하는 이니셜들이 nodes에서 어디에 존재하는지 알려준다.
* lr, lc, rr, rc : 현재 영역의 좌측 최상단 좌표(lr, lc) 와 우측 최하단 좌표(rr, rc)이다.
*/
void solve(int start, int end, int lr, int lc, int rr, int rc){
    if(start == end){
        //end condition;
        for(int r = lr; r<=rr; r++){
            for(int c= lc; c<=rc; c++){
                map[r][c] =  nodes[start].val;
            }
        }
        return;
    }

    int node_r = nodes[start].r;
    int node_c = nodes[start].c;

    for(int i = start + 1; i<=end; i++){
        if(node_r != nodes[i].r){
            // r기준 나누기
            solve(start, i-1, lr, lc, node_r, rc);
            solve(i, end, node_r+1, lc, rr, rc);
            return;
        }
    }
    //모든 r이 동일한 경우
    solve(start, start, lr, lc, rr, node_c);
    solve(start+1, end, lr, node_c+1, rr, rc);
}

int main(){
    setbuf(stdout, NULL);
    int T;
    scanf("%d", &T);
    for(int t= 1; t<T+1; t++){
        nodes.clear();
        scanf("%d %d", &R, &C);
        for(int r=0; r<R; r++){
            scanf("%s", map[r]);
        }

        // 위에서 아래로, 왼쪽에서 오른쪽으로 탐색하기에 자동 정렬되어 삽입된다.
        for(int r= 0; r<R; r++){
            for(int c= 0; c<C; c++){
                if(map[r][c] != '?'){
                    nodes.push_back({r,c,map[r][c]});
                }
            }
        }

        solve(0, nodes.size()-1, 0, 0, R-1, C-1);

        printf("Case #%d:\n", t);
        for(int r=0; r<R; r++){
            printf("%s\n", map[r]);
        }
    }
}