[알고리즘] DFS 깊이우선탐색

깊이우선탐색 DFS이란?

• 정점의 자식들을 먼저 탐색한 후 다시 원점으로 돌아가 다른 루트를 탐색하는 방식
  

• DFS 방식 : A - B - D - E - F - C - G - H - I - J
  - 한노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가면서 순회한다

그래프로 노드 표현하기

DFS의 사용

• 자동 미로 생성 또는 미로 탐색에 사용된다.
• 막다른 곳에 도달하면 막다른 길에 대한 표식을 남기고 가장 가까운 갈림길로 돌아와서 다시 탐색을 한다.
• 모든 노드를 방문한다.

DFS알고리즘 구현하기

• 자료구조 스택과 큐를 활용한다.
• need_visit 스택, visited 큐 두가지의 자료구조를 생성

인접행렬

import java.util.Scanner;

public class DFS_adjMatrix {
	private static int nV; // 정점의 개수
	private static int[][] graph; //그래프
	private static boolean[] visited; // 정점 방문 여부 체크 배열

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		nV = sc.nextInt(); // 정점의 수
		int e = sc.nextInt(); // 간선의 수
		
		// 그래프, 배열 초기화
		initGraph(nV);
		
		for (int i = 0; i < e; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			put(x, y);
		}
		printMat();
		
		System.out.print("1부터 탐색 ");
		DFS(1);
		System.out.println();
		
		clearVisited();
		System.out.print("2부터 탐색 ");
		DFS(2);
		System.out.println();
		
		clearVisited();
		System.out.print("3부터 탐색 ");
		DFS(3);
		System.out.println();
	}
	
	public static void DFS(int v) {
		visited[v] = true; // 방문했으니 true로 변경
		
		System.out.print(v + " ");
		
		for (int i = 1; i <= nV; i++) {
			if (graph[v][i] == 1 && visited[i] == false) { // 연걸되어있는 정점이 있고, 방문하지않은 정점일 경우
				DFS(i); // DFS 재귀호출
			}
		}
	}
	
	public static void printMat() {
		for(int i = 0; i < graph.length; i++) {
            for(int j=0; j < graph[i].length; j++) {
                System.out.print(" " + graph[i][j]);
            }
            System.out.println();
        }
	}
	
	public static void initGraph(int v) {
		graph = new int[v+1][v+1];
		visited = new boolean[v+1];
		
		for (int i = 0; i < v; i++) {
			visited[i] = false;
		}
	}
	
	public static void put(int x, int y) {
		graph[x][y] = graph[y][x] = 1;
	}
	
	public static void clearVisited() {
		for (int i = 0; i < visited.length; i++) {
			visited[i] = false;
		}
	}
}

인접 리스트

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class DFS_adjList {
	private static int nV; // 정점의 개수
	private static ArrayList<Integer> graph[]; // 인접리스트
	private static boolean visited[]; // 정점 방문 여부 확인

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		nV = sc.nextInt(); // 정점의 수
		int e = sc.nextInt(); // 간선의 수
		
		// 그래프, 배열 초기화
		initGraph();
		
		for (int i = 0; i < e; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			put(x, y);
		}
		printMat();
		
		System.out.print("1부터 탐색 ");
		DFS(1);
		System.out.println();
		
		clearVisited();
		System.out.print("2부터 탐색 ");
		DFS(2);
		System.out.println();
		
		clearVisited();
		System.out.print("3부터 탐색 ");
		DFS(3);
		System.out.println();
		
	}
	
	// 깊이 우선 탐색
	public static void DFS(int start) {
		if (visited[start]) return; //이미 방문했을 경우
		
		visited[start] = true;
		System.out.print(start + " ");
		for (int i : graph[start]) {
			if (!visited[i]) {
				DFS(i);
			}
		}
	}
	
	public static void clearVisited() {
		for (int i = 0; i < visited.length; i++) {
			visited[i] = false;
		}
	}
	
	public static void initGraph() {
		graph = new ArrayList[nV + 1];
		visited = new boolean[nV + 1];
		
		for (int i = 0; i <= nV; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i <= nV; i++) {
			visited[i] = false;
		}
	}
	
	public static void printMat() {
		for(int i = 0; i < graph.length; i++) {
			System.out.print(i + " -> ");
            for (int j = 0; j < graph[i].size(); j++) {
            	System.out.print(graph[i].get(j) + " ");
            }
            System.out.println();
        }
	}
	
	public static void put(int x, int y) {
		graph[x].add(y);
		graph[y].add(x);
	}

	
}

스택

시간복잡도

• 노드 수 : V
• 간선 수 : E
• 시간 복잡도 : O(V + E)