깊이우선탐색(DFS)
1.전위순회
import sys
sys.stdin=open("input.txt", "r")
def DFS(v):
if v >7:
return
else:
print(v, end=" ") #전위순회
DFS(v*2) #왼쪽 자식 호출
DFS(v*2+1) #오른쪽 자식호출
if __name__== "__main__": #스크립트실행시 가장 먼저 실행
DFS(1)
전위순회
함수 자신의 일(ex출력)을 처리한 다음에 자식노드를 호출하는 경우를 의미한다
2. 중위순회
import sys
sys.stdin=open("input.txt", "r")
def DFS(v):
if v >7:
return
else:
DFS(v*2) #왼쪽 자식 호출
print(v, end=" ") #중위순회
DFS(v*2+1) #오른쪽 자식호출
if __name__== "__main__": #스크립트실행시 가장 먼저 실행
DFS(1)
중위순회
함수가 호출되면 왼쪽자식의 일을 먼저 처리한 후에 자기자신의 일(ex출력)을 처리하는 경우를
의미한다
3. 후위순회
import sys
sys.stdin=open("input.txt", "r")
def DFS(v):
if v >7:
return
else:
DFS(v*2) #왼쪽 자식 호출
DFS(v*2+1) #오른쪽 자식호출
print(v, end=" ") #후위순회
if __name__== "__main__": #스크립트실행시 가장 먼저 실행
DFS(1)
후위순회
함수가 호출되면 왼쪽자식의 일을 처리하고, 오른쪽 자신의 일을 처리한 후 가장 나중에 자신의 일(ex출력)을 처리하는 경우를 의미한다
▶ 후위순회 -작동예시
'파이썬 알고리즘 > 완전탐색과 DFS기초' 카테고리의 다른 글
5. 바둑이 승차 - Cut Edge Tech (0) | 2022.11.07 |
---|---|
4.합이 같은 부분집합 (0) | 2022.11.06 |
3.부분집합 구하기(DFS) (0) | 2022.11.06 |
1.재귀함수를 이용한 이진수 출력 (0) | 2022.11.06 |
[선수지식] 재귀함수와 스택(Stack) (0) | 2022.11.06 |