• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 스택 또는 재귀 함수를 사용
• Cycle이나 양방향 그래프를 고려하여 visited 배열 사용 필요!!
• 이미지 출처: 나노 바나나 프로 (Nano Banana Pro)

문제 유형

• 검색 대상 그래프가 큰 경우
• 경로의 특징을 저장해둬야 하는 문제 (e.g. a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제)
• 각각의 경로마다 특징을 저장해줘야될 때

코드 예시

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	//노드갯수
	static int N = 4;
	//idx : 노드번호, val : 해당노드를 탐색한 적이 있는지 여부
	static int visited[] = new int[4];
	static int arr[][] = {
			{0,1,0,1},
			{0,0,1,0},
			{1,0,0,0},
			{0,0,0,0},
				};
	
	static void dfs(int now) {
		visited[now] = 1;
		System.out.print(now+" ");
		for(int i=0; i<N; i++) {
			//i : 다음으로 갈 수 있는 노드 번호
			//연결이 안된것임!
			if(arr[now][i] == 0)continue;
			if(visited[i] == 1)continue;
			dfs(i);
		}
	}
	
	public static void main(String[] args) {
		//탐색하는 노드 번호
	
		dfs(0);
		
	}
		
}