[코드포스 Practice20] B. OR in Matrix

어휴.. 애증의 B번...

얼른 풀고 D번으로 가려 했는데 못갔다

 

 

처음 풀 때 연산 그대로 하면 N^4 나올 것 같아서 rowa, cola 따로 빼서 연산했는데 지금 보니 N^3 밖에 안 나올 것 같아서 바로 풀어도 됐을 것 같다.

 

풀이는.. 일단 B가 0인 경우는 i, j 모두 0일거라 i, j 값을 기록해둔다.

 

다음으로 B값이 맞는지 확인한다.

 

i, j가 둘 다 0인데 B가 1이면 안되므로 NO 출력해주고

 

i, j가 둘 다 1이고 B도 1이면 그건 ans 배열에 1 적어둔다.

 

마지막으로 ans 배열 출력해주면 끝~~

 

하지만 틀렸다ㅠㅠ

 

알고보니 B -> A를 만들 때 이 자리에 반드시 1이 있어야 하는 조건은 만족하는데 이게 다시 B를 만드느냐는 확인하지 못했다

 

그래서 A -> B가 되는지 확인하는 부분이 추가로 들어갔어야 했다.

 

 

처음에 확인하는 거 어찌할지 몰라서 가로 확인 & 세로 확인 따로 만들어서 OR하려 했는디 짜다 보니 안 그래도 될 것 같았음

 

 

확인하는 부분을 추가했다

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    
    vector<vector<int>> vb(m, vector<int>(n, 0));
    vector<int> rowa(m, 1);
    vector<int> cola(n, 1);
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)   
        {
            scanf("%d", &vb[i][j]);
            if (vb[i][j] == 0)
            {
                rowa[i] = 0;
                cola[j] = 0;
            }
        }
    }
    
    vector<vector<int>> ans(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)   
        {
            if (vb[i][j] == 1 && (rowa[i] == 0 && cola[j] == 0))
            {
                printf("NO");
                return 0;
            }
            if (rowa[i] == 1 && cola[j] == 1)
                ans[i][j] = 1;
        }
    }
    
    vector<vector<int>> calc(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)   
        {
            if (ans[i][j] == 1)
            {
                for (int k = 0; k < m; k++)
                    calc[k][j] = 1;
                for (int k = 0; k < n; k++)
                    calc[i][k] = 1;
            }
        }
    }
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)   
        {
            if (calc[i][j] != vb[i][j])
            {
                printf("NO");
                return 0;
            }
        }
    }
    
    printf("YES\n");
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)   
        {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

 

 

드디어 성공~~

 

이건 북님 코드

 

거의 비슷한데 rowa, cola를 만드는 뻘짓이 안 들어갔고 (+)십자 전부 1인지 확인하는 부분을 count를 써서 확인했다.