[백준] 1260번 DFS와 BFS [Python]

• 문제 : https://www.acmicpc.net/problem/1260

 

from collections import defaultdict

n, m, v = map(int, input().split())

graph = defaultdict(list)

for i in range(m): # 양방향 그래프 구현
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(n):
    print(n, end=" ")
    visit[n] = 1
    graph[n].sort() # 숫자가 작은 노드부터 방문하기 위해 정렬

    for i in graph[n]:
        if visit[i] == 0:
            dfs(i)


def bfs(n):
    q = [graph[n]] # 시작 노드와 연결된 간선들 큐에 추가
    print(n, end=" ")
    visit[n] = 1

    while q:
        x = q.pop(0) # 간선 정보들을 큐에서 꺼냄 x = [1,2,3] 형태

        for i in x:
            if visit[i] == 0:
                print(i, end=" ")
                visit[i] = 1
                q.append(graph[i]) # 다음에 갈 간선 정보를 큐에 추가


visit = [0] * (n+1)
dfs(v) # dfs 시작

print()

visit = [0] * (n+1)
bfs(v) # bfs 시작