[14492번] 부울행렬의 부울곱

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 부울 곱

2. 행렬 곱

부울 곱 정의와 행렬 곱 알고리즘만 짤 수 있다면 해결 할 수 있다.

부울 곱은 우리가 항상 하던 행렬의 곱과 같다.

단, 한번이라도 1이나오면 그때의 idx는 1이 된다.

3
1 1 0
0 1 0
0 0 1
1 0 0
1 1 1
0 0 1

여기서 첫번째 값이 1인 이유는

1 && 1 || 1 && 1 || 0 && 0 이기에 1이다.

사실 보기에 편하기 위해 소스 코드 부분에서 chk 부울 변수를 이용하지만, 다음과 같이 해도 무방하다.

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            for (int m = 0; m < n; m++)
            {
                if (a[i][m] && b[m][j])
                {
                    cnt++;
                    break;
                }
            }
        }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int a[302][302], b[302][302];
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &b[i][j]);
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            bool chk = false;
            for (int m = 0; m < n; m++)
            {
                chk |= a[i][m] && b[m][j];
 
                if (chk)
                {
                    cnt++;
                    break;
                }
            }
        }
 
    cout << cnt;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>