[Algo] DFS 기초 예제와 코드 구현 (python)

관련 백준 문제

(1260번) DFS와 BFS

Python으로 DFS구현

인접 리스트 생성

입력 받으면서 그래프의 정점간의 관계를 나타내는 인접 리스트까지 생성해주기

n, m , v = map(int, input().split()) # n : 노드(정점), m(간선), v(시작점)

graph = [[] for _ in range(n + 1)] # 0번 노드는 사용하지 않으니 1~n번 노드까지 할당
for i in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for i in range(1, n + 1):
    graph[i].sort() # 순서 보정을 위해 오름차순 정렬 필요

DFS 함수 작성

재귀를 사용하여 구현하면 코드가 정말 간단하다

def dfs(curr):
    print(curr, end=' ')
    for nxt in graph[curr]:
        if visit[nxt] == 0:
            visit[nxt] = 1
            dfs(nxt)

전체 코드

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

# 인접 리스트
graph = [[] for _ in range(n+1)] # 1번부터 n번까지 정점 사용

# 간선 처리
for i in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1) # 단방향이면 이거 주석처리 하면 됨

for i in range(1, n+1):
    graph[i].sort() # 순서 보정을 위해 오름차순 정렬 필요

visit = [0 for _ in range(n + 1)]
visit[v] = 1

def dfs(curr):
    print(curr, end=' ')
    for nxt in graph[curr]:
        if visit[nxt] == 0:
            visit[nxt] = 1
            dfs(nxt)

dfs(v)