문제 분석

본 문제는 두 개의 n×m 이진 행렬 A와 B가 주어졌을 때, B 행렬이 특정 규칙에 따라 A 행렬로부터 생성되었는지 확인하는 문제이다.

생성 규칙: B[i][j]는 A 행렬의 i번째 행 전체와 j번째 열 전체에 대해 OR 연산을 수행한 결과값이다.

OR 연산의 특성을 먼저 파악해야 한다:

0|0 = 0
0|1 = 1
1|0 = 1
1|1 = 1

핵심 관찰

OR 연산의 특성을 통해 두 가지 중요한 결론을 도출할 수 있다:

결론 1: B[i][j]가 0이라면, 해당 위치의 행과 열에 해당하는 A 행렬의 모든 원소가 0이어야 한다. 왜냐하면 OR 연산에서 하나라도 1이 있으면 결과가 1이 되기 때문이다.

결론 2: B[i][j]가 1이라면, 해당 행 또는 열 중 최소 하나 이상이 1을 포함해야 한다. 이는 역으로 A 행렬의 해당 행과 열을 검증하는 데 사용된다.

알고리즘

위 결론을 바탕으로 다음과 같은 접근법을 사용한다:

1. 초기 행렬 A를 모두 1로 설정한다
2. B에서 0이出现的 위치에 대해 A의 해당 행과 열을 모두 0으로 설정한다
3. B에서 1이 나타나는 위치를 확인하여 A의 해당 행과 열에 최소 하나의 1이 있는지 검증한다
4. 검증에 실패하면 "NO"를, 성공하면 "YES"와 가능한 A 행렬을 출력한다

구현 코드

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAX_SIZE 500

using namespace std;

int n, m;
int matrixB[MAX_SIZE][MAX_SIZE];
int matrixA[MAX_SIZE][MAX_SIZE];
bool isValid;

int main() {
    cin >> n >> m;
    
    // 초기값을 1로 설정
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            matrixA[i][j] = 1;
        }
    }
    
    // B 행렬 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrixB[i][j];
        }
    }
    
    // B[i][j] == 0인 경우, 해당 행과 열을 0으로 설정
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrixB[i][j] == 0) {
                // 열을 0으로
                for (int row = 0; row < n; row++) {
                    matrixA[row][j] = 0;
                }
                // 행을 0으로
                for (int col = 0; col < m; col++) {
                    matrixA[i][col] = 0;
                }
            }
        }
    }
    
    // B[i][j] == 1인 경우, 해당 행과 열에 1이 존재하는지 확인
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrixB[i][j] == 1) {
                bool foundOneInColumn = false;
                bool foundOneInRow = false;
                
                // 열에서 1 탐색
                for (int row = 0; row < n; row++) {
                    if (matrixA[row][j] == 1) {
                        foundOneInColumn = true;
                        break;
                    }
                }
                
                // 행에서 1 탐색
                for (int col = 0; col < m; col++) {
                    if (matrixA[i][col] == 1) {
                        foundOneInRow = true;
                        break;
                    }
                }
                
                if (!foundOneInColumn && !foundOneInRow) {
                    cout << "NO";
                    return 0;
                }
            }
        }
    }
    
    // 결과 출력
    cout << "YES" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << matrixA[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

복잡도 분석

본 알고리즘은 세 번의 순회 과정을 거치며, 각 과정은 O(n × m)의 시간 복잡도를 가진다. 따라서 총 시간 복잡도는 O(n × m)이며,额外的 추가 공간은 O(n × m)이다.