[백준 16976번] [구현] 배열 복원하기

사실.. 처음 풀 때 순간적으로 착각하여 오래 풀게 되었다.

 

단순히 옮기는 것이므로, 각 component에 해당하는 숫자가 그대로 노출되어 있는 부분이 반드시 존재할 것으로 착각하였으나 그렇지 않은 부분도 있었다.

 

대표적인 예시가

3 4 1 1
1 2 3 4 0
5 7 9 11 4
9 15 17 19 8
0 9 10 11 12

이다. 이 경우에는 6, 7 부분이 직접적으로 나오지는 않는다.

 

따라서 풀이방법은 다음과 같다.

1. 덧셈이 아니라 직접적으로 노출된 부분을 store한다. (단, 해당 배열의 default 상태를 -1로 두어 저장된 것인지 아닌지를 구분한다.)

2. 겹치는 부분을 기준으로 찾되, 더해진 2개의 index값 중 default 상태에서 변화된 부분이 있으면 그것을 통해 나머지 index에 해당하는 값을 추론한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;

    int temporary_store[600][600];
    int restore[300][300];

    for(int i = 0; i < 300; i++){
        for(int j = 0; j < 300; j++){
            restore[i][j] = -1;
        }
    }


    for(int i = 0; i < H + X; i++){
        for(int j = 0; j < W + Y; j++){
            int temp;
            cin >> temp;
            temporary_store[i][j] = temp;
        }
    }

    // 위 
    for(int i = 0; i < X; i++){
        for(int j = 0; j < W; j++){
            restore[i][j] = temporary_store[i][j];
        }
    }

    // 아래
    for(int i = H; i < X + H; i++){
        for(int j = Y; j < W + Y; j++){
            restore[i - X][j - Y] = temporary_store[i][j];
        }
    }
    
    // 오른쪽 옆
    for(int i = X; i < H; i++){
        for(int j = W; j < W + Y; j++){
            restore[i - X][j - Y] = temporary_store[i][j];
        }
    }

    // 왼쪽 옆
    for(int i = X; i < H; i++){
        for(int j = 0; j < Y; j++){
            restore[i][j] = temporary_store[i][j];
        }
    }

    // 나머지 체크(겹치는 부분 체크)
    for(int i = X; i < H; i++){
        for(int j = Y; j < W; j++){
            // 만약 여기가 -1이 아닌 경우
            if(restore[i][j] != -1){
                restore[i - X][j - Y] = temporary_store[i][j] - restore[i][j];
            }
            else{
                restore[i][j] = temporary_store[i][j] - restore[i - X][j - Y];
            }
        }
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W - 1; j++){
            cout << restore[i][j] << " ";
        }
        cout << restore[i][W - 1];
        cout << "\n";
    }

    return 0;
}