[Graph] DFS와 BFS

import sys
from collections import deque

n, m, start = map(int, sys.stdin.readline().split())
graph = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x][y] = graph[y][x] = 1

b_visited = [0]*(n+1)
d_visited = [0]*(n+1)

def BFS(start):
    print()
    q = deque()
    
    q.append(start)
    b_visited[start] = 1
    
    while q:
        node = q.popleft()
        print(node, end=" ")
    
        for i in range(1, n+1):
            if b_visited[i]==0 and graph[node][i]==1:
                q.append(i)
                b_visited[i] = 1

def DFS(node):
    d_visited[node] = 1
    print(node, end=" ")

    for i in range(1, n+1):
        if d_visited[i]==0 and graph[node][i]==1:
            DFS(i)

DFS(start)
BFS(start)

DFS

재귀를 사용해서 매번 출력하고 연결된 노드를 끝까지 먼저 방문

BFS

인접한 노드를 먼저 방문하며 출력하고 연결된 노드를 append

visited는 모두 0으로 생성하고 방문 시 인덱스에 맞춰 1로 변경
연결된 노드 표현하는 graph를 딕셔너리보다 2차원 배열로 표현하면 성능 향상
graph를 딕셔너리로 표현하면 sort도 필요
출력이 모든 방문 노드 순서라면 반복문 돌면서 출력