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
- 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
Author And Source
이 문제에 관하여(DFS 1DAY), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@refindmysapporo/DFS-1DAY저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)