DFS(Depth-first Search) / BFS(Breadth-first Search)

오늘은 많은 코딩테스트의 단골 문제인 알고리즘 DFS, BFS에 대해서 정리해보도록 하겠다.

 

1. 그래프 탐색

- 비선형 구조 : 표현된 모든 자료를 빠짐없이 검색하는 것이 중요

- 알고리즘1 : 깊이우선탐색 - DFS(Depth First Search, DFS)

- 알고리즘2 : 너비우선탐색 - BFS(Breadth First Search, BFS)

 

 

 

 

2. DFS(Depth-first Search, 깊이우선탐색)

깊은 것를 우선으로 탐색을 수행하는 방법

방문처리 시에(스택에 넣을 때) print

(1) 개요

① 시작 정점의 "한 방향"으로 "갈 수 있는 경로가 있는 곳까지" 깊이 탐색

② 더 이상 갈 곳 없다면, 가장 마지막에 만났던 "갈림길 간선이 있는 정점"으로 되돌아 옴

→ 되돌아가기 위해서는 후입선출 구조의 Stack이 필요

③ 다른 방향의 정점으로 탐색을 반복하여 모든 정점을 방문하여 순회

 

 

(2) 알고리즘 (Stack이 empty가 될 때까지 반복)

알고리즘 순서도

① 스택을 활용한 DFS

- int[][] a : 각 정점 기준의 인접행렬 (인접리스트로 구현 가능 _ 복잡하지만 공간복잡도 절약)

- boolean[] c : 방문 여부를 check하는 boolean 배열

- int v : 방문할 정점 (지정해준 시작 정점 & stack.peek() )

- flag : 방문하지 않은 정점의 유무를 check

public static void DFS(int[][] a, boolean[] c, int v) {
	Stack<Integer> stk = new Stack<>();
	int length = a.length - 1;
	stk.push(v); c[v] = true; //시작점 v 방문
	System.out.print(v+" ");
	boolean flag = false; //이어서 방문할 정점 없음으로 초기화
	while(!stk.isEmpty()) {
		v = stk.peek();
		flag = false;
		for(int i = 1; i <= length; i++) {
			if(a[v][i] == 1 && !c[i]) { //방문 안 한 w 하나 선택
				stk.push(i); c[i] = true; //w 방문
				System.out.print(i+" "); //push하자마자 출력
				flag = true; //이어서 방문할 정점 있음
				break;
			}
		}
		if(!flag) { //v 기준으로 방문 안 한 w가 없으면 pop하여 상위로
			stk.pop();
		}
	}
}

 

② 재귀를 활용한 DFS

public static void DFS(int[][] a, boolean[] c, int v) {
	boolean[] check = new boolean[a.length];
	int length = a.length - 1;
	c[v] = true; // v점 방문
	System.out.print(v + " ");
	for(int i = 1; i <= length; i++) {
		if(a[v][i] == 1 && !c[i])	DFS(a, c, i); //방문 안 한 w찾으면 해당 점에서 DFS 진행
	}
}

 

 

 

 

3. BFS(Breadth-First Search)

너비를 우선으로 탐색을 수행하여 '최단 경로'를 보장하는 방법

큐에서 꺼냈을 때 print

(1) 개요

① 시작 정점과 인접한 정점들을 모두 차례로 방문

② 방문했던 정점들을 시작점으로 하여 다시 인접한 정점들 모두 차례로 방문

→ 방문했던 정점들을 큐에 보관하여 먼저 들어온 정점부터 시작점으로 채택

③ 큐가 완전히 빌 때까지 반복 (isEmpty())

 

 

 

(2) 알고리즘

public static void BFS(int[][] a, boolean[] c, int v) { //그래프, 방문체크, 시작 정점
	Queue<Integer> qu = new LinkedList<>();
	int size = a.length-1;
	qu.add(v);
	c[v] = true;
	while(!qu.isEmpty()) {
		v = qu.poll(); //시작점 선정과 동시에 deQueue
        	System.out.print(v + " "); //큐에서 꺼냈을 때 print
		for(int i = 1; i <= size; i++) {
			if(a[v][i] == 1 && !c[i]) { //인접한 정점 모두 방문(DFS와 다르게 break, flag x)
				qu.add(i);
				c[i] = true;
			}
		}
	}
}

 

 

 

 

 

 

 

 

 

(출처)

swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AV1847saI78CFAZN