[LeetCode] 1582. Special Positions in a Binary Matrix

https://leetcode.com/problems/special-positions-in-a-binary-matrix/description/

Special Positions in a Binary Matrix - LeetCode

leetcode - Special Positions in a Binary Matrix

문제 유형 : 행렬

문제 난이도 : Easy

13일연속 Easy... 릿코드의 크리스마스 선물인가?

 

문제

Given an m x n binary matrix mat, return the number of special positions in mat.

A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

 

m*n의 바이너리 행렬 mat가 주어집니다. 특별한 위치들의 개수를 구하시오.

mat[i][j]가 1이고 같은 행과 열의 값은 모두 0인 경우, 위치(i, j)는 특별하다.

 

풀이

m*n의 행렬을 순회하면서, 1을 발견하면 그 행과 열을 탐색하면서, 유일한 1인지 확인해주면 된다.

 

코드

C++

class Solution {
public:
    int check(vector<vector<int>> &mat, int row, int col) {
        int mask = 0;
        for(int i = 0; i < mat.size(); i++) {
            if(i == row) continue;
            mask |= mat[i][col];
            if(mask) return 0;
        }

        for(int j = 0; j < mat[0].size(); j++) {
            if(j == col) continue;
            mask |= mat[row][j];
            if(mask) return 0;
        }

        return 1;
    }

    int numSpecial(vector<vector<int>>& mat) {
        const int m = mat.size();
        const int n = mat[0].size();
        int cnt = 0;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][j] == 1) {
                    cnt += check(mat, i, j);
                }
            }
        }

        return cnt;
    }
};