•
문제 링크 : 
LeetCodeFlood Fill - LeetCode
•
문제 설명 : 제공된 image 행렬에서 시작 포인트((sr, sc))부터 4방향에 존재하는 같은 색깔을 모두 제시된 컬러 값으로 변경한다.
•
풀이 방법
◦
4방향의 좌표를 확인하여, 아래 조건이 모두 만족하면 추가 탐색하였다
▪
현 위치와 동일한 컬러 값
▪
새로운 좌표가 image 행렬 내 있을 때
▪
아직 방문한적이 없는 좌표일 때
•
시간복잡도 :
•
성공 코드
물론 이와 같이, 주변 정보를 탐색하는 경우는 BFS로 하는게 더 적합할 수 있다.
하지만, 이와 같이 DFS로 한번 풀어보았다.
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
visit = set()
self.color_change(image, color, sr, sc, visit)
return image
def color_change(self, image, color, x, y, visit):
visit.add((x, y))
if 0 <= x - 1 < len(image) and image[x][y] == image[x - 1][y] and (x - 1, y) not in visit:
self.color_change(image, color, x - 1, y, visit)
if 0 <= x + 1 < len(image) and image[x][y] == image[x + 1][y] and (x + 1, y) not in visit:
self.color_change(image, color, x + 1, y, visit)
if 0 <= y - 1 < len(image[0]) and image[x][y] == image[x][y - 1] and (x, y - 1) not in visit:
self.color_change(image, color, x, y - 1, visit)
if 0 <= y + 1 < len(image[0]) and image[x][y] == image[x][y + 1] and (x, y + 1) not in visit:
self.color_change(image, color, x, y + 1, visit)
image[x][y] = color
Python
복사