글 읽기 - [python3] DFS, BFS 왜 틀린건가요??

rtd8653 4년 전 0

예제들 다 맞고 여러 가지 테스트 해봤는데, 왜 틀린건지 모르겠어여 ㅠㅠㅠㅠㅠㅠ

도와줘요 ㅠㅠㅠㅠㅠ

info = input().split(" ")
[N, M, root] = [int(x) for x in info]

table = [set() for _ in range(N)] # 'set' in order to prevent multiple same entries

for _ in range(M): # make a table for edges from every node to node
    edge = input().split(" ")
    ends = [int(x) for x in edge]
    table[ends[0]-1].add(ends[1])
    table[ends[1]-1].add(ends[0])

for row in table:
    row = list(row) # change 'set' to 'list' for sorting
    row.sort() # elements should be sorted by increasing order

def DFS(start):
    DFS_order.append(start)
    if len(table[start-1]) == 0:
        return
    for cur in table[start-1]: # for every node connected to the root node
        if cur not in DFS_order:
            DFS(cur) # search recursively

def BFS(root):
    searching = [root]
    BFS_order.append(root)
    while(len(searching)!=0): # iterate with increasing degree of searching
        new_searching = []
        for node in searching:
            for cur in table[node-1]: # for every node 1)connected to current node
                if cur not in BFS_order: # and 2)having not been searched yet
                    BFS_order.append(cur) # search the node
                    new_searching.append(cur) # and use it in the next iteration
        searching = new_searching

# DFS TRAVERSING
DFS_order = []
DFS(root)

# BFS TRAVERSING
BFS_order = []
BFS(root)

## print the space-seperated nodes by searched order
print(*DFS_order)
print(*BFS_order)