문제 소개
흑백 픽셀로만 구성된 그림이 주어졌을 때, 아래 두 가지 규칙을 모두 만족하는 '외로운 검은 픽셀'의 개수를 찾아야 합니다.
- 해당 픽셀이 위치한 행 R과 열 C에는 정확히 N개의 검은 픽셀이 존재해야 합니다.
- 열 C에 검은 픽셀을 가진 모든 행은 행 R과 완전히 동일해야 합니다.
그림은 검은 픽셀을 의미하는 'B'와 흰 픽셀을 의미하는 'W'로 구성된 2차원 char 배열로 표현됩니다.
예시로 이해하기
다음과 같은 입력이 주어지고 N = 3이라고 가정해 보겠습니다.
| W | B | W | B | B | W |
| W | B | W | B | B | W |
| W | B | W | B | B | W |
| W | W | B | W | B | W |
이때 출력 결과는 6입니다. 1번 열과 3번 열에 있는 모든 'B'가 조건을 만족하는 외로운 픽셀이기 때문입니다.
예를 들어 R = 0, C = 1인 위치의 'B'를 살펴보겠습니다.
- 규칙 1: 행 R = 0과 열 C = 1에는 각각 정확히 N(=3)개의 'B' 픽셀이 존재합니다.
- 규칙 2: 열 C = 1에 'B' 픽셀을 가진 행은 0행, 1행, 2행이며, 이 세 행은 모두 행 R = 0과 완전히 동일합니다.
풀이 접근 방법
이 문제는 다음 단계를 거쳐 해결할 수 있습니다.
- 정답을 저장할 변수 ret을 0으로 초기화합니다.
- 행별로 검은 픽셀의 열 인덱스를 저장하는 맵 r과, 열별로 검은 픽셀의 행 인덱스를 저장하는 맵 c를 선언합니다.
- n은 행의 개수, m은 열의 개수로 설정합니다.
- 배열 전체를 순회하면서 p[i][j]가 'B'라면 r[i]에 j를, c[j]에 i를 삽입하여 각 행과 열의 검은 픽셀 정보를 기록합니다.
- 다시 배열을 순회하면서 p[i][j]가 'B'이고, r[i]의 크기와 c[j]의 크기가 모두 N과 같은 경우를 찾습니다.
- 조건을 만족하면 ok를 true로 설정하고, c[j]에 포함된 각 행 x에 대해 r[x]와 r[i]가 동일한지 확인합니다. 하나라도 다르면 ok를 false로 바꾸고 반복을 종료합니다.
- 검사를 통과하면 ret을 1 증가시킵니다.
- 모든 탐색이 끝나면 최종적으로 ret을 반환합니다.
C++ 구현 코드
아래는 위 알고리즘을 C++로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findBlackPixel(vector<vector<char>>& p, int N) {
int ret = 0;
unordered_map <int, set <int> > r, c;
int n = p.size();
int m = p[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(p[i][j] == 'B'){
r[i].insert(j);
c[j].insert(i);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m && r.count(i); j++){
if(p[i][j] == 'B' && r[i].size() == N && c[j].size() == N){
bool ok = true;
for(auto& x : c[j]){
if(r[x] != r[i]){
ok = false;
break;
}
}
ret += ok;
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<char>> v = {{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','W','B','W','B','W'}};
cout << (ob.findBlackPixel(v, 3));
}
실행 결과
입력:
{{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','W','B','W','B','W'}}, 3출력:
6