[Algorithm] DFS 기법 설명 및 활용

1. DFS(Depth First Search) - 깊이 우선 탐색

- 그래프 전체를 탐색하는 방법 중 하나

- 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법

- 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방법

- 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 함

- 완전 탐색, 길찾기, 그래프 순회 등등에 사용

 

 

2. 예시 문제

문제)

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

풀이)

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


public class Main {
	static boolean[][] graph;
	static boolean[] visited;
	static int result;
	
	static void bfs(int start,int N) {
		Queue<Integer> queue = new LinkedList<Integer>();
		StringBuilder sb = new StringBuilder();
		queue.add(start);
		visited[start] = true;
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			sb.append(tmp+" ");
			for(int i=1;i<=N;i++) {
				if(graph[tmp][i] && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
		System.out.println(sb);
	}
	static void dfs_rec(int start, int N) {
		visited[start] = true;
		System.out.print(start+" ");
		for(int i=1;i<=N;i++) {
			if(graph[start][i] && !visited[i])
				dfs_rec(i,N);
		}
	}
	static void dfs_stack(int start, int N) {
		Stack<Integer> stack = new Stack<Integer>();
		int tmp = start;
		stack.push(start);
		visited[start] = true;
		System.out.print(start+" ");
		while(!stack.isEmpty()) {
			int num = stack.pop();
			for(int i=1;i<=N;i++) {
				if(graph[tmp][i] && !visited[i]) {
					tmp = i;
					visited[i] = true;
					stack.push(i);
					System.out.print(i+" ");
				}
			}
		}
		System.out.println();
	}
    public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int N,M,V;
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	V = Integer.parseInt(st.nextToken());
    	
    	graph = new boolean[N+1][N+1];
    	visited  = new boolean[N+1];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int from,to;
    		from = Integer.parseInt(st.nextToken());
    		to = Integer.parseInt(st.nextToken());
    		graph[from][to] = graph[to][from] = true;
    	}
    	
    	
    	//dfs_stack(V,N);//스택 dfs
    	dfs_rec(V,N);//재귀 dfs
    	System.out.println();
    	Arrays.fill(visited, false);
    	bfs(V,N);
    }
}