BOJ 17963 - Projection 링크
(2024.03.24 기준 G1)

문제

$n \times m \times h$ 크기의, $1 \times 1 \times 1$ 큐브로 이루어져 있는 3D 물체를 앞쪽과 옆쪽으로 투영한 그림자의 형태가 주어진다.

가능한 3D 물체 중, 가장 큐브가 많이 놓여져 있는 3D 물체와 가장 큐브가 적게 놓여져 있으며 사전순으로 가장 앞서는 3D 물체의 큐브 위치를 출력

알고리즘

3D 기하학으로 생각해야 하는 구현 문제

풀이

앞쪽으로 투영한 그림자의 모습은 $nm$, 옆쪽으로 투영한 그림자의 모습은 $nh$라 하자.

일단 가장 큐브가 많이 놓여져 있는 3D 물체인 $maximum$을 구해보자.

$maximum$은 최대한 큐브를 놓아야 하므로 가능한 모든 위치헤 모두 큐브를 놓아야 한다.
다른 말로는 두 투영이 모순이 되지 않는 모든 위치에 큐브를 놔둬야 한다.
그러면 두 투영을 살펴봤을 때, 그림자가 있지 않은 곳은 절대 큐브가 위치할 수 없다. 그러므로 일단 절대 큐브가 위치할 수 없는 곳부터 걸러내자.

그런데 이 문제는 두 투영이 모순인 경우도 주어진다. 그러므로 절대 큐브가 위치할 수 없는 곳을 걸러낸 다음, 다음 두 사항으로 확인하자.

• $nm[i][j] = 1(0 \le i < n; 0 \le j < m)$일 때, $(i, j, 0)$, $(i, j, 1)$, $\dots$, $(i, j, h-1)$ 중 한 곳에는 꼭 큐브가 위치할 수 있는가?
• $nh[i][k] = 1(0 \le i < n; 0 \le k < h)$일 때, $(i, 0, k)$, $(i, 1, k)$, $\dots$, $(i, m-1, k)$ 중 한 곳에는 꼭 큐브가 위치할 수 있는가?

위를 만족한다면 이제 구해놓은 가능한 위치를 모두 출력하면 된다.

이제 가장 큐브가 적게 놓여져 있으며 사전순으로 가장 앞서는 3D 물체인 $minimum$을 구해보자.

일단 모든 $i(0 \le i < n)$마다, $nm[i][j] = 1(0 \le j < m)$인 모든 $j$를 $idx_m[i]$ 배열에, $nh[i][k] = 1(0 \le k < h)$인 모든 $k$를 $idx_h[i]$ 배열에 담자.

배열에 담긴 인덱스들은 꼭 필요한 인덱스들이라고 할 수 있다. 이제 이들을 최소한으로 하려면 이분 매칭느낌으로 앞에서부터 짝지으면 된다. 이때 개수가 맞지 않으면 그만큼, 개수가 큰 것의 첫 인덱스부터 하나씩 개수가 적은 것의 첫 인덱스와 짝지으면 된다.

설명이 너무 어려우니, 예를 들어보겠다.
$idx_m[i]$ 배열은 $[0, 1, 2]$, $idx_h[i]$ 배열은 $[0, 1, 3, 5, 7]$이라고 생각해보자.
그러면 $idx_h[i]$ 배열의 크기가 $2$만큼 크다. 그러므로 $idx_m[i]$ 배열의 첫 인덱스인 $0$과, $idx_h[i]$ 배열의 첫 $2$개 만큼 짝지어주고, 이제 남은 인덱스들을 짝지어주면 $(i, 0, 0)$, $(i, 0, 1)$, $(i, 0, 3)$, $(i, 1, 5)$, $(i, 2, 7)$이 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int> tiii;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, h; cin >> n >> m >> h;
    string nm[n]; for (int i = 0; i < n; i++) cin >> nm[i];
    string nh[n]; for (int i = 0; i < n; i++) cin >> nh[i];

    // maximum을 구하자.
    // 가능한 위치에 모두 큐브를 놔두면 된다.
    // 그림자가 있지 않은 곳은 절대 큐브가 위치할 수 없다.
    // 일단 절대 큐브가 위치할 수 없는 곳부터 걸러내자.
    // matrix[i][j][k] : (i, j, k)에 큐브가 위치할 수 있다면 1, 아니면 0.
    int matrix[n][m][h]; fill(&matrix[0][0][0], &matrix[n - 1][m - 1][h], 1);

    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        if (nm[i][j] == '0') // (i, j, 0), (i, j, 1), ..., (i, j, h-1)에는 큐브가 위치할 수 없다.
            for (int k = 0; k < h; k++) matrix[i][j][k] = 0;

    for (int i = 0; i < n; i++) for (int k = 0; k < h; k++)
        if (nh[i][k] == '0') // (i, 0, k), (i, 1, k), ..., (i, m-1, k)에는 큐브가 위치할 수 없다.
            for (int j = 0; j < m; j++) matrix[i][j][k] = 0;

    // 두 투영이 모순인지 확인해야 한다.
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){
        if (nm[i][j] == '0') continue;

        // (i, j, 0), (i, j, 1), ..., (i, j, h-1) 중 한 곳에는 꼭 큐브가 위치할 수 있어야 한다.
        bool valid = false;
        for (int k = 0; k < h; k++) if (matrix[i][j][k]){
            valid = true;
            break;
        }
        if (!valid){
            cout << -1;
            return 0;
        }
    }

    for (int i = 0; i < n; i++) for (int k = 0; k < h; k++){
        if (nh[i][k] == '0') continue;

        // (i, 0, k), (i, 1, k), ..., (i, m-1, k) 중 한 곳에는 꼭 큐브가 위치할 수 있어야 한다.
        bool valid = false;
        for (int j = 0; j < m; j++) if (matrix[i][j][k]){
            valid = true;
            break;
        }
        if (!valid){
            cout << -1;
            return 0;
        }
    }

    // 구해놓은 가능한 위치를 모두 출력한다.
    vector<tiii> ans;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < h; k++)
        if (matrix[i][j][k]) ans.push_back({i, j, k});
    cout << ans.size() << '\n';
    for (auto [i, j, k]: ans) cout << i << ' ' << j << ' ' << k << '\n';

    // minimum을 구하자.
    // 사전순으로 가장 앞서며, 개수가 가장 적게 하려면
    // i번째 줄마다 두 투영의 있어야 하는 위치들을 앞에서부터 짝지으면 된다.
    // 이때 개수가 맞지 않으면 그만큼, 개수가 큰 것의 첫 인덱스부터 하나씩 개수가 적은 것의 첫 인덱스와 짝지으면 된다.
    // ex. [0, 1, 2], [0, 1, 3, 5, 7] -> (0, 0), (0, 1), (0, 3), (1, 5), (2, 7)
    ans.clear();
    vector<int> idx_m, idx_h;
    for (int i = 0; i < n; i++){
        idx_m.clear(); idx_h.clear();
        for (int j = 0; j < m; j++) if (nm[i][j] == '1') idx_m.push_back(j);
        for (int k = 0; k < h; k++) if (nh[i][k] == '1') idx_h.push_back(k);
        if (idx_m.empty() && idx_h.empty()) continue; // 한 곳에만 있으면 모순이므로 이미 걸러진 상태이다.
        int idx1 = 0, idx2 = 0;
        if (idx_m.size() > idx_h.size()){
            while (idx_m.size() - idx1 > idx_h.size() - idx2) ans.push_back({i, idx_m[idx1++], idx_h[idx2]});
        }
        else{
            while (idx_m.size() - idx1 < idx_h.size() - idx2) ans.push_back({i, idx_m[idx1], idx_h[idx2++]});
        }
        while (idx1 < idx_m.size()) ans.push_back({i, idx_m[idx1++], idx_h[idx2++]});
    }
    cout << ans.size() << '\n';
    for (auto [i, j, k]: ans) cout << i << ' ' << j << ' ' << k << '\n';
}

• Python

import sys; input = sys.stdin.readline

n, m, h = map(int, input().split())
nm = [input().strip() for _ in range(n)]
nh = [input().strip() for _ in range(n)]

# maximum을 구하자.
# 가능한 위치에 모두 큐브를 놔두면 된다.
# 그림자가 있지 않은 곳은 절대 큐브가 위치할 수 없다.
# 일단 절대 큐브가 위치할 수 없는 곳부터 걸러내자.
# matrix[i][j][k] : (i, j, k)에 큐브가 위치할 수 있다면 1, 아니면 0.
matrix = [[[1] * h for _ in range(m)] for _ in range(n)]

for i in range(n):
    for j in range(m):
        if nm[i][j] == '0': # (i, j, 0), (i, j, 1), ..., (i, j, h-1)에는 큐브가 위치할 수 없다.
            for k in range(h):
                matrix[i][j][k] = 0

for i in range(n):
    for k in range(h):
        if nh[i][k] == '0': # (i, 0, k), (i, 1, k), ..., (i, m-1, k)에는 큐브가 위치할 수 없다.
            for j in range(m):
                matrix[i][j][k] = 0

# 두 투영이 모순인지 확인해야 한다.
for i in range(n):
    for j in range(m):
        if nm[i][j] == '0':
            continue

        # (i, j, 0), (i, j, 1), ..., (i, j, h-1) 중 한 곳에는 꼭 큐브가 위치할 수 있어야 한다.
        valid = False
        for k in range(h):
            if matrix[i][j][k]:
                valid = True
                break
        if not valid:
            print(-1)
            exit()

for i in range(n):
    for k in range(h):
        if nh[i][k] == '0':
            continue

        # (i, 0, k), (i, 1, k), ..., (i, m-1, k) 중 한 곳에는 꼭 큐브가 위치할 수 있어야 한다.
        valid = False
        for j in range(m):
            if matrix[i][j][k]:
                valid = True
                break
        if not valid:
            print(-1)
            exit()

# 구해놓은 가능한 위치를 모두 출력한다.
ans = []
for i in range(n):
    for j in range(m):
        for k in range(h):
            if matrix[i][j][k]:
                ans.append((i, j, k))
print(len(ans))
for i, j, k in ans:
    print(i, j, k)

# minimum을 구하자.
# 사전순으로 가장 앞서며, 개수가 가장 적게 하려면
# i번째 줄마다 두 투영의 있어야 하는 위치들을 앞에서부터 짝지으면 된다.
# 이때 개수가 맞지 않으면 그만큼, 개수가 큰 것의 첫 인덱스부터 하나씩 개수가 적은 것의 첫 인덱스와 짝지으면 된다.
# ex. [0, 1, 2], [0, 1, 3, 5, 7] -> (0, 0), (0, 1), (0, 3), (1, 5), (2, 7)
ans = []
for i in range(n):
    idx_m = [j for j in range(m) if nm[i][j] == '1']
    idx_h = [k for k in range(h) if nh[i][k] == '1']
    if not idx_m and not idx_h: # 한 곳에만 있으면 모순이므로 이미 걸러진 상태이다.
        continue
    idx1 = 0; idx2 = 0
    if len(idx_m) > len(idx_h):
        while len(idx_m) - idx1 > len(idx_h) - idx2:
            ans.append((i, idx_m[idx1], idx_h[idx2]))
            idx1 += 1
    else:
        while len(idx_m) - idx1 < len(idx_h) - idx2:
            ans.append((i, idx_m[idx1], idx_h[idx2]))
            idx2 += 1
    while idx1 < len(idx_m):
        ans.append((i, idx_m[idx1], idx_h[idx2]))
        idx1 += 1; idx2 += 1
print(len(ans))
for i, j, k in ans:
    print(i, j, k)