[Python] 깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth First Search)

• 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면
  이전 정점으로 돌아간다.

• 재귀를 이용한다.

• check 배열을 만들어 한번 방문한 경로는 방문했다고 체크를 해야 한다.

• 이동한 정점의 값을 가지고 계속 연산을 하는 문제에서 많이 사용한다.

• 모든 경로를 탐색한다.

현재 정점 : 1
순서 : 1
스택 : 1



현재 정점 : 2
순서 : 1 2
스택 : 1 2



현재 정점 : 3
순서 : 1 2 3
스택 : 1 2 3



현재 정점 : 4
순서 : 1 2 3 4
스택 : 1 2 3 4



현재 정점 : 5
순서 : 1 2 3 4 5
스택 : 1 2 3 4 5



• 5에서 더 이상 갈 곳이 없으므로 4로 돌아간다.
현재 정점 : 4
순서 : 1 2 3 4 5
스택 : 1 2 3 4



현재 정점 : 6
순서 : 1 2 3 4 5 6
스택 : 1 2 3 4 6



• 6에서 더 이상 갈 곳이 없으므로 4로 돌아간다.
현재 정점 : 4
순서 : 1 2 3 4 5 6
스택 : 1 2 3 4



• 4에서 더 이상 갈 곳이 없으므로 3으로 돌아간다.
현재 정점 : 3
순서 : 1 2 3 4 5 6
스택 : 1 2 3



• 3에서 더 이상 갈 곳이 없으므로 2로 돌아간다.
현재 정점 : 2
순서 : 1 2 3 4 5 6
스택 : 1 2



• 2에서 더 이상 갈 곳이 없으므로 1로 돌아간다.
현재 정점 : 1
순서 : 1 2 3 4 5 6
스택 : 1



• 스택이 비어있으므로 탐색 종료
현재 정점 : 1
순서 : 1 2 3 4 5 6
스택 :

n,m=map(int,input().split())
map_=[list(map(int,input())) for _ in range(n)]
check=[[False for _ in range(m)] for _ in range(n) ]
print(map_)
print(check)


dx=[0,0,1,-1]
dy=[-1,1,0,0]


def dfs(x,y):
    if check[x][y]==False:
        check[x][y]=True

    for k in range(4):
        nx,ny=x+dx[k],y+dy[k]
        if 0<=nx<n and 0<=ny<m:
            if check[nx][ny]==False and map_[nx][ny]==0:
                dfs(nx,ny)
    return True

result=0
for i in range(n):
    for j in range(m):
        if map_[i][j]==0 and check[i][j]==False:
            if dfs(i,j):
             
                result += 1

print(result)

dfs로 구역 나누기 기본 코드