[백준][DFS/BFS] 1260. DFS와 BFS (2)(파이썬/Python)

from collections import  deque

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

#vertex 개수만큼 그래프를 초기화해준다. 앞에 []는 0번째 vertex는 없기 때문
graph = [[] for _ in range(n+1)]

#방문처리를 위한 visited 자료구조 준비
#처음엔 모두 False로 만들고 방문하게 될 떄 True로 돌려준다.
visited = [False] * (n+1)

for i in range(m):
    a, b = map(int,input().split())
    # 입력 받을 때 vertex번호대로 넣어주기 위함
    # Ex) [[], [2,3,4], [1,4], [1,4], [1,2,3]] 0번 1번 2번 3번 4번 vertex를 표현
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

def DFS(graph,v,visited):
    visited[v] = True
    print(v,end=" ")
    for i in graph[v]:
        if not visited[i]:
            DFS(graph,i,visited)
            
def BFS(graph, v, visited):
    visited = [False] * (n + 1)
    queue = deque([v])
    visited[v] = True
    while queue:
        pop = queue.popleft()
        print(pop, end=' ')
        for i in graph[pop]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True



DFS(graph,v,visited)
print()
BFS(graph,v,visited)

# 두 알고리즘의 가장 큰 차이점은 DFS의 경우 재귀호출을 사용해서 확인하던 vertex의 다른 연결값이 있으면 그 값을 가서 확인하고 방문처리하고 또 다시 방문하여 확인처리 하는 것이다.

# BFS의 경우엔 만약 1번 노드를 확인할 땐 1번 노드의 인접 노드들을 먼저 다 확인 한 뒤 그 다음 인접 노드를 확인하는 방식으로 진행된다.

DFS의 흐름

 

BFS의 흐름

#방문처리가 끝나면 확인할 필요 없이 queue에 들어가 있는 순서대로 출력해주면 된다.