[알고리즘/백준] 1260번 : DFS와 BFS(python)

예제는 맞게 나오는데 계속 틀렸다고 나와서 찾아보니 set형은 정렬이 보장되지 않는다는걸 처음 알았다. 따라서 extend부분에서 정렬을 해주었다.

from collections import deque


def make_graph(N, M):
    graph = dict()
    for i in range(N):
        graph[i + 1] = set()
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)
    return graph


def dfs(V, graph):
    visited = list()
    q = list()
    q.append(V)
    while q:
        node = q.pop()
        if node not in visited:
            q.extend(sorted(list(graph[node]), reverse=True))
            visited.append(node)
    print(*visited)


def bfs(V, graph):
    visited = list()
    q = deque()
    q.append(V)
    while q:
        node = q.popleft()
        if node not in visited:
            q.extend(sorted(list(graph[node])))
            visited.append(node)
    print(*visited)


if __name__ == "__main__":
    N, M, V = map(int, input().split())
    graph = make_graph(N, M)
    dfs(V, graph)
    bfs(V, graph)