DFS

목차
- 인접리스트
- 인접행렬

인접리스트

# 입력
n,m,s=map(int,input().split()) #n-노드갯수, m-입력갯수, s-시작정점
adj_list=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    adj_list[a].append(b)
    adj_list[b].append(a)
    
    
#####################################################
visited=[None]*(n+1)

# DFS 함수 정의
def dfs(v):
    adj_list[v].sort() #노드번호가 작은순부터 탐색할경우
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v)
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in adj_list[v]:
        if not visited[i]:
            dfs(i)
            
print('[DFS 방문순서]')
dfs(s)

 

인접행렬

# 입력
n, m, s = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
  f, t = map(int, input().split())
  matrix[f][t] = matrix[t][f] = 1

################################################
def dfs(v):
  visited[v] = True
  print(v)
  for i in range(len(matrix[v])):
    if matrix[v][i] == 1 and not visited[i]:
      dfs(i)


dfs(s)