[BOJ] 2009 - Minecraft

https://www.acmicpc.net/problem/2009

BOJ - Minecraft

문제 유형: 구현, 그리디, 해 구성하기

문제 난이도: Silver II

시간 제한: 1.52초

메모리 제한: 1024MB

 

문제

2009년은 전 세계 게이머들이 사랑하는 게임인 Minecraft가 출시된 해입니다. 그동안 Minecraft에서 쌓은 추억을 회상하며 흐즈로는 다음 문제를 떠올렸습니다.

 n×n×n의 3차원 격자 M을 생각합시다. 그 중 i번째 층, j번째 행, k번째 열의 칸은 Mi,j,k로 표기하며, 각 칸에는 블록이 최대 한 개 존재합니다. 해당하는 칸에 블록이 한 개 있다면 Mi,j,k=1, 없다면 Mi,j,k=0으로 표기합니다. 축에 나란한 3개의 평면에 격자의 상태를 사영한 n×n의 2차원 격자를 각각 H, R, C라고 합시다. 각각의 격자를 엄밀히 정의하면 다음과 같습니다.

•  j번째 행 k번째 열에 블록이 적어도 하나 존재한다면, Hj,k=1입니다. 그렇지 않다면 Hj,k=0입니다.
•  i번째 층 k번째 열에 블록이 적어도 하나 존재한다면, Ri,k=1입니다. 그렇지 않다면 Ri,k=0입니다.
•  i번째 층 j번째 행에 블록이 적어도 하나 존재한다면, Ci,j=1입니다. 그렇지 않다면 Ci,j=0입니다.

여러분에게 세 격자 H′, R′, C′가 주어집니다. 여러분은 3차원 격자를 사영한 결과가 H=H′, R=R′, C=C′가 되는 3차원 격자 M′이 존재하는지 확인하는 프로그램을 만들어야 합니다.

 

입력

첫 번째 줄에 격자의 한 변의 크기를 나타내는 정수 n이 주어집니다. (1≤n≤100)

두 번째 줄부터 n개의 줄에 걸쳐 각 줄에 0과 1로 이루어진 길이 n의 문자열이 주어집니다. 그 중 j번째 줄의 k번째 문자는 Hj,k′의 값입니다.

 n+2번째 줄부터 n개의 줄에 걸쳐 각 줄에 0과 1로 이루어진 길이 n의 문자열이 주어집니다. 그 중 i번째 줄의 k번째 문자는 Ri,k′의 값입니다.

 2n+2번째 줄부터 n개의 줄에 걸쳐 각 줄에 0과 1로 이루어진 길이 n의 문자열이 주어집니다. 그 중 i번째 줄의 j번째 문자는 Ci,j′의 값입니다.

 

출력

조건을 만족하는 격자 M′가 존재한다면 한 줄에 YES를 출력합니다. 그 다음 줄부터 출력해야 할 내용은 다음과 같습니다.

 n×n의 격자를 총 n번 출력합니다. 각각의 격자를 출력할 때는 n개의 줄에 걸쳐 각 줄에 0과 1로 이루어진 길이 n의 문자열을 출력합니다. i번째 격자의 j번째 줄 k번째 문자는 출력할 격자의 한 칸 Mi,j,k′에 대응됩니다. 가능한 격자 M′가 여러 개 존재한다면 그 중 하나만 출력합니다.

조건을 만족하는 격자 M′가 존재하지 않는다면 한 줄에 NO를 출력합니다.

 

풀이

사영 결과별로 최대한 1을 남기는식으로 구성해준다.

그 뒤, 사영 결과와 만들어진 격자 M'을 비교하며 사영에 차이가 있다면 NO를 아니면 정답을 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vector<vector<vector<int>>> mask(n,
                                     vector<vector<int>>(n, vector<int>(n, 1)));
    vector<string> H, R, C;

    for (int j = 0; j < n; j++) {
        string temp;
        cin >> temp;
        H.emplace_back(temp);

        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                mask[i][j][k] = mask[i][j][k] && (temp[k] - '0');
            }
        }
    }

    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        R.emplace_back(temp);

        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                mask[i][j][k] = mask[i][j][k] && (temp[k] - '0');
            }
        }
    }

    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        C.emplace_back(temp);

        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                mask[i][j][k] = mask[i][j][k] && (temp[j] - '0');
            }
        }
    }

    vector<vector<int>> h(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (mask[i][j][k]) h[j][k] |= 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (h[i][j] != H[i][j] - '0') {
                cout << "NO\n";
                return 0;
            }
        }
    }

    vector<vector<int>> r(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (mask[i][j][k]) r[i][k] |= 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (r[i][j] != R[i][j] - '0') {
                cout << "NO\n";
                return 0;
            }
        }
    }

    vector<vector<int>> c(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (mask[i][j][k]) c[i][j] |= 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (c[i][j] != C[i][j] - '0') {
                cout << "NO\n";
                return 0;
            }
        }
    }

    cout << "YES\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                cout << mask[i][j][k];
            }
            cout << "\n";
        }
    }

    return 0;
}