DFS 1DAY

1.FLOODFILL

제일 기초적인 문제로 DFS의 관점을 생각할 수 있었다.

from collections import deque
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        q=deque()
        k = image[sr][sc]
        direction = [(0,1) ,(0,-1),(1,0),(-1,0)]
        q.append((sr,sc))
        if image[sr][sc]==newColor : return image
        def dfs():
            while q :
                x,y=q.popleft()
                if 0<=x<len(image) and 0<=y<len(image[0]):
                    if image[x][y]==k :
                        image[x][y]=newColor
                        for i in range(4):
                            dx=x+direction[i][0]
                            dy=y+direction[i][1]
                            q.append((dx,dy))
                       
        dfs()
        return image
        

2. NUMBER OF ISLAND
   배열 요소가 순회할 때마다 땅인지 강인지 판단하여 땅이면 다 강으로 바꾸는 형태로 로직을 짰다

# 아이디어는 이차원 배열을 순회하면서 1인 즉 섬인 값이 있을 떄 DFS 시작
# DFS에서 1인 값을 탐색하면서 찾은 1인 값들을 0으로 처리 강으로 만들어버림
from collections import deque
class Solution(object):
    def numIslands(self, grid):
        q=deque()
        direction=[(0,1),(0,-1),(1,0),(-1,0)]
        answer=0
        def dfs():
            while q:
                x,y=q.popleft()
                if 0<=x<len(grid) and 0<=y<len(grid[0]):
                    if grid[x][y] =="1":
                        grid[x][y]="0"
                        for i in range(4):
                            dx= x+direction[i][0]
                            dy= y+direction[i][1]
                            q.append((dx,dy))
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j]=="1" :
                    q.append((i,j))
                    dfs()
                    answer+=1
        return answer