깊이 우선 탐색 DFS

백준 11725

깊이 우선 탐색 DFS

: 그래프의 시작 노드에서 출발해 탐색할 분기를 정하여 최대 깊이까지 탐색한 후 다른 쪽 분기로 이동하여 다시 탐색

기능 : 그래프 완전 탐색
시간복잡도 : O(Node+Edge)
자료구조 : 스택(FILO)에 기초 실제로는 재귀 함수로 구현

그래프가 아닌 문제 해결

1. 백트래킹 문제
2. 재귀적 문제
3. 순열/조합

DFS 로직

• 노드 방문 여부를 체크할 배열 visited 필요
• 그래프는 인접 리스트로 표현

1. 그래프를 인접 리스트로 표현, 방문 배열 초기화
2. dfs 함수는 매개변수로 현재 노드 값과 depth 값을 가짐
3. dfs 함수에 종료 조건을 지키면 return 되도록 설정
4. 현재 노드의 visited을 바꾸기
5. for문으로 인접 리스트를 돌면서 방문하지 않았을 경우 dfs 함수로 재귀
6. for문이 끝나면 다른 분기도 돌아야 하므로 visited를 false로 다시 바꾸기

백준 11725

import java.util.*;

public class Main {

	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] parent;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt();
		//int E = sc.nextInt();
		
		// 인접 리스트
		graph = new ArrayList<>();

		// 초기화
		for (int i = 0; i < V + 1; i++) {
			graph.add(new ArrayList<>());
		}

		int x, y;
		for (int i = 0; i < V - 1; i++) {
			x = sc.nextInt();
			y = sc.nextInt();
			// 양방향
			graph.get(x).add(y);
			graph.get(y).add(x);
		}

		// 방문한 노드 배열
		visited = new boolean[V + 1];
		
		parent = new int[V + 1];
		
		dfs(1,0);
		
		for (int i = 2; i < V + 1;i++) {
			System.out.println(parent[i]);
		}
		sc.close();

	}

	static void dfs(int now, int depth) {
		visited[now] = true;
		
		for (int next : graph.get(now)) {
			if (!visited[next]) {
				parent[next] = now;
				dfs(next, depth + 1);
			}
		}
        //Backtracking할때(되돌아갈때) 필요
		//visited[now] = false;

	}

}