[백준] 1260번 DFS와 BFS / 파이썬(python)

# 문제 링크

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

# Soultion

dfs와 bfs에 대해 알면 쉽게 풀 수 있는 문제이다.

주의) 인접한 노드가 작은 순으로 방문한다고 했으므로, 13,28번째 줄처럼 sorted()를 이용하여 오름차순 정렬해준다. 

n,m,v = map(int,input().split())
graph = [[] * n for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
visited = [0] * (n+1)
def dfs(v):
    print(v,end=' ')
    global visited, graph
    visited[v] = 1
    for i in sorted(graph[v]):
        if visited[i]!=1:
            dfs(i)
dfs(v)
print()
from collections import deque
visited = [0] * (n+1)
def bfs(start):
    global visited, graph
    queue = deque([start])
    visited[start] = 1
    
    while queue:
        v = queue.popleft()
        print(v,end=' ')
        for i in sorted(graph[v]):
            if visited[i]!=1:
                queue.append(i)
                visited[i] = 1
bfs(v)