그래프 구현

n = int(input()) # 노드 개수
v = int(input()) # 엣지 개수

# 그래프 생성 (인덱스 0 사용 안 하는 경우)
graph = [[] for i in range(n + 1)] # 그래프 초기화
visited = [0] * (n + 1) # 방문 여부 표시
for i in range(v): # 그래프 생성
    a, b = map(int, input().rstrip().split())
    graph[a] += [b] # a에 b 연결
    graph[b] += [a] # b에 a 연결 -> 양방향

깊이우선탐색 DFS

Depth First Search

1. 첫 노드 방문
2. 이웃 노드들에 대해
   3-1. 방문하지 않은 노드라면 1-3 반복
   3-2. 방문한 노드면 패스

• 재귀 이용

def dfs(v):
    visited[v] = 1
    for nx in graph[v]:
        if visited[nx] == 0:
            dfs(nx)

너비우선탐색 BFS

Breadth First Search

1. 시작점을 방문 처리 후 큐에 넣기
2. 큐가 비어있지 않는 동안 아래 반복
   3-1. 가장 먼저 들어온 노드 뽑기
   3-2. 해당 노드의 이웃들에 대해 방문하지 않았다면 큐에 넣고 방문 처리
   3-3. 방문 했다면 패스

• 큐 이용

from collections import deque

visited[시작점] = 1 # 시작점 방문 처리
Q = deque([시작점]) # 시작점
while Q:
    node = Q.popleft()
    for nx in graph[node]:
        if visited[nx] == 0:
            Q.append(nx)
            visited[nx] = 1