[LeetCode] 531. Lonely Pixel I

531. Lonely Pixel I

Medium

Given an m x n picture consisting of black 'B' and white 'W' pixels, return the number of black lonely pixels.

A black lonely pixel is a character 'B' that located at a specific position where the same row and same column don't have any other black pixels.

 

Example 1:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

Example 2:

Input: picture = [["B","B","B"],["B","B","W"],["B","B","B"]]
Output: 0

 

Constraints:

• m == picture.length
• n == picture[i].length
• 1 <= m, n <= 500
• picture[i][j] is 'W' or 'B'.

---

문제 풀이

• W, B 로 이루어진 메트릭스에서 B 가 혼자 있는 곳의 갯수를 구해야한다.
• 혼자 있다는 뜻은, 가로 세로 즉, 행열에 B 가 없는 것을 의미한다. 
• 두 가지 방법이 있다. 

• 첫 번째
  • B 위치에서 상하 좌우로 움직여, B 가 나올 경우 정답의 갯수에 추가하지 않는다. 
  • 좌표를 이동 시킬때는 Out of Index 에러가 나지 않도록 주의하자
• 두 번째
  • 행, 열의 배열을 미리 만들어 놓는다.
  • 모든 값들을 확인하면서 해당 행, 열에 B 가 몇개 있는지 숫자를 늘려준다.
  • 그때 B 의 좌표를 저장 해놓는다.
  • 마지막에 저장해 놓은 B 의 좌표를 모두 확인하면서 행과 열에 자기 자신만 있다면 답에 추가해준다.

소스 코드

첫 번째

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        pixels = []
        ans = 0
        dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        ylen = len(picture)
        xlen = len(picture[0])
        for i in range(ylen):
            for j in range(xlen):
                if picture[i][j] == 'B':
                    f = 0
                    for t in range(4):
                        nxy = i
                        nxx = j
                        while nxy > -1 and nxy < ylen and nxx > -1 and nxx < xlen:
                            nxy += dic[t][0]
                            nxx += dic[t][1]
                            if nxy < 0 or nxy >= ylen or nxx < 0 or nxx >= xlen:
                                continue
                            if picture[nxy][nxx] == 'B':
                                f = 1
                                break
                        if f == 1: break
                    if f == 0: 
                        ans += 1

두 번째 

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        ylen = len(picture)
        xlen = len(picture[0])
        yCnt = [0] * ylen
        xCnt = [0] * xlen
        ans = 0
        bList = []
        for i in range(ylen):
            for j in range(xlen):
                if picture[i][j] == 'B':
                    yCnt[i] += 1
                    xCnt[j] += 1
                    bList.append((i, j))
        for i, j in bList:
                if picture[i][j] == 'B' and yCnt[i] == 1 and xCnt[j] == 1:
                        ans += 1
        return ans