파이썬에서 BFS, DFS 구현 시 주의사항(재귀 X)

인접 노드를 저장하기 위한 리스트를 만들 때 클래스 변수로 선언하는 경우를 조심해야한다.

하나의 클래스의 인스턴스들이 클래스 변수를 공유하기 때문에 각자의 인접노드를 개별적으로 갖고있지 않게 된다.

따라서 self를 사용해서 각자 인접한 노드를 저장하도록 하자.

'''
그래프 검색
DFS : 이어진 자식 노드 단위로 검색하는 방법, 트리 순회 방식도 포함, 스택사용
BFS : 레벨 단위로 검색하는 방법, 큐 사용

그래프 구성
노드, 엣지, 인접노드들은 링크드리스트로 연결되어있다.
'''
from queue import Queue
import copy
class node :
    def __init__(self, v):
        self.ad = list()
        self.v = v
        self.mark = False #스택 또는 큐에 들어갔는지 마킹할 플래그 변수

def add_edge(n1, n2):
    if n2 not in n1.ad:
        n1.ad.append(n2)
    
    if n1 not in n2.ad:
        n2.ad.append(n1)

def dfs(nodes, idx):
    root = nodes[idx]
    stack = list()
    stack.append(root)
    root.mark = True
    while(stack):
        r = stack.pop()
        if len(r.ad):
            for n in r.ad:
                if n.mark == False:
                    stack.append(n)
                    n.mark = True
        print(r.v)

def bfs(nodes, idx):
    root = nodes[idx]
    queue = Queue()
    queue.put(root)
    root.mark = True
    while(queue):
        r = queue.get()
        if len(r.ad):
            for n in r.ad:
                if n.mark == False:
                    queue.put(n)
                    n.mark=True
        print(r.v)

if __name__=='__main__':
    start = int(input())
    nodes = []
    for i in range(9):
        nodes.append(node(i))
    add_edge(nodes[0], nodes[1])
    add_edge(nodes[1], nodes[2])
    add_edge(nodes[1], nodes[3])
    add_edge(nodes[2], nodes[3])
    add_edge(nodes[3], nodes[4])
    add_edge(nodes[3], nodes[5])
    add_edge(nodes[5], nodes[6])
    add_edge(nodes[5], nodes[7])
    add_edge(nodes[6], nodes[8])
    
    bfs_nodes = copy.deepcopy(nodes)
    print('DFS','='*20)
    dfs(nodes, start)
    print('BFS','='*20)
    bfs(bfs_nodes, start)