[LeetCode] 733번 Flood Fill 문제 풀이 (파이썬)

https://leetcode.com/problems/flood-fill/

Flood Fill - LeetCode

분명 어려운 문제는 아닌데 아직도 bfs에 완전히 익숙해지지가 않아서 꽤 헤맸다. 특히, dx, dy로 리스트를 만들어놓고 다른 노드를 방문하는 방법이 아직 익숙하지 않아 우선은 중복되고 장황한 while문을 썼다.

또한, 처음에는 visited 리스트를 따로 만들려고 했으나, 풀다보니 굳이 그럴 필요 없이 방문한 곳의 값을 입력받은 color 값으로 변경해주면 된다는 것을 깨달았다.

마지막으로, starting pixel의 값이 color의 값과 애초에 같다면 탐색할 필요 없이 바로 종료하면 된다. 이 점을 간과하면 시간 초과에 걸리게 되니 주의할 것.

# 초안

from collections import deque # bfs 문제이므로 deque 임포트하기

class Solution:
    # 아래 두 함수에서 사용할 클래스 변수 선언
    image: [[int]]
    m: int
    n: int
    num: int
    color: int
    
    def bfs(self, start_i , start_j):
        queue = deque([(start_i, start_j)]) # 큐에 starting pixel의 인덱스 튜플을 넣어준다.
        self.image[start_i][start_j] = self.color # starting pixel의 색상 값을 변경해준다.
        
        # 수정하려는 부분 - while loop (이유: 너무 장황하고 중복되는 코드가 많음)
        while queue: # 큐에 요소가 남아있는 한
            i, j = queue.popleft() # 너비 우선 탐색을 위해 맨 앞의 요소를 꺼내준다.
            
            # 사면으로 이웃하는 노드들을 방문하여 starting pixel의 초깃값과 같다면 1) 큐에 넣고 2) 색상 값을 변경해준다.
            if i - 1 >= 0 and self.image[i - 1][j] == self.num:
                queue.append((i - 1, j))
                self.image[i - 1][j] = self.color
            if i + 1 < self.m and self.image[i + 1][j] == self.num:
                queue.append((i + 1, j))
                self.image[i + 1][j] = self.color
            if j - 1 >= 0 and self.image[i][j - 1] == self.num:
                queue.append((i, j - 1))
                self.image[i][j - 1] = self.color
            if j + 1 < self.n and self.image[i][j + 1] == self.num:
                queue.append((i, j + 1))
                self.image[i][j + 1] = self.color
            
    
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        # 클래스 변수들 초기화
        self.image = image
        self.m = len(image)
        self.n = len(image[0])
        self.num = self.image[sr][sc]
        self.color = color
        
        if self.num != self.color: # self.num == self.color이면 탐색할 필요 없이 바로 종료하면 된다.
            self.bfs(sr, sc)
        
        return self.image # 따로 visited 리스트 없이 self.image 값들 자체를 변경하므로 이를 바로 리턴하면 됨

dx, dy 리스트로 while문의 중복을 줄인 코드:

from collections import deque

class Solution:
    image: [[int]]
    m: int
    n: int
    num: int
    color: int
    
    def bfs(self, start_i , start_j):
        queue = deque([(start_i, start_j)])
        self.image[start_i][start_j] = self.color
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        
        while queue:
            i, j = queue.popleft()
            for turn in range(4): # 상, 하, 좌, 우 총 4번의 이동 각각에 대하여
                new_i, new_j = i + dx[turn], j + dy[turn]
                if 0 <= new_i < self.m and 0 <= new_j < self.n and self.image[new_i][new_j] == self.num:
                    queue.append((new_i, new_j))
                    self.image[new_i][new_j] = self.color
            
    
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        self.image = image
        self.m = len(image)
        self.n = len(image[0])
        self.num = self.image[sr][sc]
        self.color = color
        
        if self.num != self.color:
            self.bfs(sr, sc)
        
        return self.image

한편, 연결된 노드들을 탐색하는 것이기 때문에 dfs로도 풀 수 있다.