C++로 풀어보는 외로운 픽셀(Lonely Pixel) 문제 I

문제 소개

검은색 픽셀과 흰색 픽셀로만 이루어진 그림이 주어졌을 때, 외로운 검은 픽셀(black lonely pixel)의 개수를 찾는 것이 이번 문제의 목표입니다. 그림은 검은 픽셀을 나타내는 'B'와 흰 픽셀을 나타내는 'W'로 구성된 2차원 char 배열로 표현됩니다.

외로운 검은 픽셀이란, 자신이 속한 행과 열 어디에도 다른 검은 픽셀이 존재하지 않는 위치에 있는 'B'를 의미합니다.

예를 들어 입력이 아래와 같다고 가정해 보겠습니다.

W	W	B
W	B	W
B	W	W

이때 출력은 3입니다. 세 개의 'B'가 서로 다른 행과 서로 다른 열에 위치하고 있어, 모두 외로운 검은 픽셀에 해당하기 때문입니다.

풀이 전략

이 문제는 별도의 카운팅 배열을 새로 할당하지 않고, 그림 배열의 첫 번째 행과 첫 번째 열을 카운터로 재활용하는 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

'B'를 발견하면, 해당 열의 검은 픽셀 개수를 첫 번째 행(picture[0][j])에 누적합니다.
마찬가지로 해당 행의 검은 픽셀 개수는 첫 번째 열(picture[i][0])에 누적하되, 첫 번째 행 자체의 개수는 별도 변수(firstRow)로 관리합니다.
문자 값을 1씩 증가시키는 방식으로 개수를 인코딩하므로, 값이 'C'(원래 'B'에서 1 증가) 또는 'X'(원래 'W'에서 1 증가)라면 그 행·열에 검은 픽셀이 정확히 하나 있다는 뜻이 됩니다.

알고리즘 단계

n := 그림의 행(row) 크기
m := n이 0이 아니면 열(column) 크기, 그렇지 않으면 0
ret := 0, firstRow := 0 으로 초기화
첫 번째 순회 (i: 0 ~ n-1, j: 0 ~ m-1):
- picture[i][j]가 'B'이면:
- picture[0][j]가 'Y' 미만이면서 'V'가 아니면 picture[0][j]를 1 증가 (열 카운트 기록)
- i가 0이면 firstRow를 1 증가, 그렇지 않고 picture[i][0]이 'Y' 미만이면서 'V'가 아니면 picture[i][0]을 1 증가 (행 카운트 기록)
두 번째 순회 (i: 0 ~ n-1, j: 0 ~ m-1):
- picture[i][j]가 'W' 미만(즉, 원래 'B'였던 칸)이고, picture[0][j]가 'C' 또는 'X'(그 열에 검은 픽셀이 정확히 1개)이면:
- i가 0이면, ret := (ret + firstRow가 1이면 1, 아니면 0)
- 그렇지 않고 picture[i][0]이 'C' 또는 'X'(그 행에 검은 픽셀이 정확히 1개)이면 ret을 1 증가
ret 반환

이 방식은 전체 그림을 두 번만 순회하므로 시간 복잡도는 O(n × m)이며, 추가 배열을 사용하지 않아 공간 복잡도는 O(1)입니다.

예제 코드

아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = picture.size();
        int m = n ? picture[0].size() : 0;
        int ret = 0;
        int firstRow = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B') {
                    if (picture[0][j] < 'Y' && picture[0][j] != 'V'){
                        picture[0][j]++;
                    }
                    if (i == 0)
                        firstRow++;
                    else if (picture[i][0] < 'Y' && picture[i][0] != 'V') {
                        picture[i][0]++;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] < 'W' && (picture[0][j] == 'C' || picture[0][j] == 'X')) {
                    if (i == 0)
                        ret += firstRow == 1 ? 1 : 0;
                    else if (picture[i][0] == 'C' || picture[i][0] == 'X')
                        ret++;
                }
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<char>> v = {{'W','W','B'},{'W','B','W'},{'B','W','W'}};
    cout << (ob.findLonelyPixel(v));
}

입력

{{'W','W','B'},{'W','B','W'},{'B','W','W'}}