DFS 개념

DFS(Depth First Serch) 알고리즘

그래프 탐색 기법 중 하나로, 깊이를 우선적으로 탐색하는 방식이다.

그래프의 특정 지점(노드)에서 출발하여 연결된 모든 노드를 방문하는 방식으로 재귀 호출을 사용한다.

문제 해결 방법 단계

1. 그래프 표현: 주로 인접 리스트나 인접 행렬을 사용하여 그래프를 표현한다.
2. 방문여부 체크: 노드를 중복 방문하지 않도록 방문 여부를 체크한다.
3. 재귀 함수 정의: DFS는 재귀적으로 탐색을 진행하며, 현재 노드에서 다음으로 이동할 수 있는 노드를 탐색한다.

• 인접 리스트?
  • 그래프를 표현하는 방법 중 하나로, 각 노드가 연결된 다른 노드들을 리스트로 저장하는 방식이다.
  • 인접 리스트는 그래프의 각 노드에 대해 그 노드와 연결된 이웃 노드들을 기록한 자료 구조임

DFS의 기본 재귀 구현

graph = [
    [],         # 0번 노드는 사용하지 않음
    [2, 3, 8],  # 1번 노드와 연결된 노드들
    [1, 7],     # 2번 노드와 연결된 노드들
    [1, 4, 5],  # 3번 노드와 연결된 노드들
    [3, 5],     # 4번 노드와 연결된 노드들
    [3, 4],     # 5번 노드와 연결된 노드들
    [7],        # 6번 노드와 연결된 노드들
    [2, 6, 8],  # 7번 노드와 연결된 노드들
    [1, 7]      # 8번 노드와 연결된 노드들
]

# 각 노드의 방문 여부를 기록할 리스트(노드가 8개이므로 9칸)
visited = [False] * 9

def dfs_recursive(graph, v, visited):
	# 현재 노드 방문 처리
	visited[v] = True
	print(v, end=' ')  # 방문한 노드 출력
	
	for i in graph[v]:
		if not visited[i]:  # 방문하지 않은 노드라면,
			dfs_recursive(graph, i, visited)  # 재귀함수를 호출한다.

코딩 테스트에서 유용한 팁

1. 입력 형식에 맞추기: 코딩 테스트 문제에서 그래프가 주어질 때, 인접 리스트나 인접 행렬로 변환하는 것이 필요할 수 있다.
2. 재귀 깊이 제한: 파이썬은 기본적으로 재귀 깊이가 제한되어 있으므로, 문제가 깊은 재귀를 요구할 경우 sys.setrecursionlimit() 을 사용해 재귀 깊이를 조절할 수 있다.