BFS, DFS

트리를 탐색하는 방식이다. 방식인데 이제 하나는 수직으로 가고(DFS), 다른 하나는 수평으로 가는(BFS) 방식이다. 둘 다 공통적으로 없는 길을 만들어서 가지 않고, 모든 트리를 순회하는데 그냥 순서가 다소 다른 것 뿐이다.

 

참고로 오늘 올리는 건 특정 노드를 찾아가는 게 아니라 전체 순회다. 특정 노드만 찾는건 나중에 레전자 DLC 다 밀고 시간 좀 되면 해드림… 지금 DLC 미느냐고 정신없다…

---

공통: 트리 생성

# 트리도 연결 리스트로 만든다...
# 그래서 노드
class Node:
    def __init__ (self, _value):
        # 관리할 값
        self.value = _value
        # 부모
        self.parent = None
        # 자식 리스트
        self.childlist = []

    def add_child(self, child_node):
        # 자식 노드 추가
        self.childlist.append(child_node)
        # 부모 연결 설정
        child_node.parent = self

트리에는 부모와 자식이라는 개념이 존재한다. 마치 가계도같은거다. 그래서 노드에도 내 자식이 누구이고, 내 부모가 누구인지를 기록해야 하는 '데'… 이게 트리는요… 하늘이 두쪽나도 부모 노드는 하나임. 두개일수가 없음. 그래프는 부모자식 개념이 없는 대신 정점에 여럿이 연결될 수 있지만 트리는 아닙니다. 그래서 부모는 변수고 자식은 리스트인 것. 자식이 두개인 경우가 이진트리인거지, 자식이 없거나 하나거나 셋 이상일 수도 있다.

 

nodeA = Node('A') # root 
nodeB = Node('B')
nodeC = Node('C')
nodeD = Node('D')
nodeE = Node('E')
nodeF = Node('F')
nodeG = Node('G')
nodeH = Node('H')
nodeI = Node('I')
nodeJ = Node('J')
nodeK = Node('K')
nodeM = Node('M')
nodeN = Node('N')

# A-B/C
nodeA.add_child(nodeB)
nodeA.add_child(nodeC)

# B-D/E
nodeA.childlist[0].add_child(nodeD)
nodeA.childlist[0].add_child(nodeE)

# C-F/G
nodeA.childlist[1].add_child(nodeF)
nodeA.childlist[1].add_child(nodeG)

# E-H/I
nodeA.childlist[0].childlist[1].add_child(nodeH)
nodeA.childlist[0].childlist[1].add_child(nodeI)

# I-J/K
nodeA.childlist[0].childlist[1].childlist[1].add_child(nodeJ)
nodeA.childlist[0].childlist[1].childlist[1].add_child(nodeK)

# D-M/N
nodeA.childlist[0].childlist[0].add_child(nodeM)
nodeA.childlist[0].childlist[0].add_child(nodeN)

아무튼 그래서 트리 맞다.

 

DFS

기본 코드

# 위에 저 트리를 DFS로 탐색해보자. 
def DFS (_rootnode, _search_list):
    # 전달받은 노드는 방문한 것으로 취급한다. 
    _search_list.append(_rootnode)
    # 현재 루트 노드의 자식 노드들을 가지고 반복함
    for subnode in _rootnode.childlist:
        # 방문기록이 없다->함수를 다시 호출
        if subnode not in _search_list: 
            DFS(subnode, _search_list)

# 탐색 결과
search_list = []
DFS(nodeA, search_list)
for subnode in search_list:
    print(f'{subnode.value}')

일단 내가 노드를 하나 방문하면, 걔는 방문한 노드로 친다, 그라고 그 밑에 노드들을 가지고 방문하고, 기록하고를 반복하는 방식이다. 이게 그림이 있으면 이해하기가 편한데 아무튼… 재귀함수가 제일 깔끔함.

 

출력 형식 수정

# 위에 저 트리를 DFS로 탐색해보자. 
def DFS (_rootnode, _search_list, _depth = 0):
    indent = "ㆍ" * _depth
    print(f'{indent} {_depth}단계: {_rootnode.value}')
    # 전달받은 노드는 방문한 것으로 취급한다. 
    _search_list.append((_rootnode.value, _depth))
    # 현재 루트 노드의 자식 노드들을 가지고 반복함
    for subnode in _rootnode.childlist:
        DFS(subnode, _search_list, _depth+1)

# 탐색 결과
search_list = []
DFS(nodeA, search_list)

우리가 그래도 이왕 출력하는거, 좀 보기 좋게 출력하면 좋잖아요... 저 위에꺼 출력하면 걍 값만 나와서 이게 몇단계인지 몰라...

 

 0단계: A
ㆍ 1단계: B
ㆍㆍ 2단계: D
ㆍㆍㆍ 3단계: M
ㆍㆍㆍ 3단계: N
ㆍㆍ 2단계: E
ㆍㆍㆍ 3단계: H
ㆍㆍㆍ 3단계: I
ㆍㆍㆍㆍ 4단계: J
ㆍㆍㆍㆍ 4단계: K
ㆍ 1단계: C
ㆍㆍ 2단계: F
ㆍㆍ 2단계: G

깃헙에 올라가있는 건 이 버전이다.

 

BFS

기본 코드

# BFS
# DFS가 수직이라면 얘는 수평이다. 탐색할 때 인접한 노드 리스트를 다 담아둔다. (방문한, 방문할 두개)

def BFS(_rootnode, _search_list, _depth = 0):
    # 방문'한' 노드
    gone_list = [_rootnode]
    # 방문'할' 노드
    will_going_list = []
    while True:
        for gone in gone_list:
            _search_list.append(gone)
            # 인접한 노드들을 담는다
            will_going_list.extend(gone.childlist)
        # 가고 나면 갱신
        gone_list.clear()
        gone_list.extend(will_going_list)
        _depth += 1
        will_going_list.clear()
        # 더 갈 거 없으면 종료
        if len(gone_list) == 0:
            break

# 탐색 결과
search_list = []
BFS(nodeA, search_list)
for subnode in search_list:
    print(f'{subnode.value}')

얘는 뭐 재귀함수고 자시고 할 것도 없고 걍 돌면서 인접한 노드들 목록에 담고 순회하고 하면 된다. 근데 이 방식은 리스트 제때 초기화 안 하면 무한루프 터짐…

 

출력 형식 수정

# BFS
# DFS가 수직이라면 얘는 수평이다. 탐색할 때 인접한 노드 리스트를 다 담아둔다. (방문한, 방문할 두개)

def BFS(_rootnode, _search_list):
    # 방문'한' 노드
    gone_list = [_rootnode]
    # 방문'할' 노드
    will_going_list = []
    # 단계(깊이)
    depth = 0
    while True:
        print(f"\n[Level {depth}]")
        for gone in gone_list:
            _search_list.append(gone)
            print(f"- {gone.value}")
            # 인접한 노드들을 담는다
            will_going_list.extend(gone.childlist)
        # 가고 나면 갱신
        gone_list.clear()
        gone_list.extend(will_going_list)
        will_going_list.clear()
        depth += 1

        # 더 갈 거 없으면 종료
        if len(gone_list) == 0:
            break

search_list = []
BFS(nodeA, search_list)

얘도 깊이 표시해주는 건 맞는데 DFS랑 출력 형식이 좀 다르다.

 

[Level 0]
- A

[Level 1]
- B
- C

[Level 2]
- D
- E
- F
- G

[Level 3]
- M
- N
- H
- I

[Level 4]
- J
- K

개인적으로는 DFS쪽 뷰가 깔끔하게 잘 나온듯...