[DFS/BFS] 개념정리3 - DFS과 BFS

그래프 탐색이란? → 하나의 정점을 시작으로 다수의 정점을 방문하는 것

DFS(Depth First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘임

사용 자료구조 : 스택

동작 과정 :

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리함
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리 함
3. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
4. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함

—> 방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미함

—> 일반적으로 인접 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순위부터 처리함

—> 탐색 순서 : 스택에서 pop된 순

 

구현방식(2가지)

A. 재귀함수로 구현

import java.util.LinkedList;

public class Main {

	public static boolean[] visited = new boolean[9]; //방문 처리를 위한 배열 
	public static LinkedList<LinkedList<Integer>> graph = new LinkedList<LinkedList<Integer>>(); //그래프 - 인접리스트로 구현 
	
	//그래프 간선 추가 (단방향 그래프)
	public static void addEdge(LinkedList<LinkedList<Integer>> graph, int u, int v) {
		graph.get(u).add(v);
	}
	
	//DFS - 재귀함수로 구현 
	public static void dfs(int startVertex) {
		//현재 노드 방문 처리 
		visited[startVertex] = true;
		System.out.print(startVertex + " ");
		//현재 노드와 인접한 다른 노드를 재귀적으로 방문함
		for(int vertex : graph.get(startVertex))
			if(!visited[vertex]) dfs(vertex);
	}
	
	public static void main(String[] args) {
		
		//그래프 초기화
		for(int i = 0; i < 9; i++)
			graph.add(new LinkedList<Integer>()); //각 정점의 연결 리스트 생성 
		
		//그래프 간선 추가 
		addEdge(graph, 1, 2);
		addEdge(graph, 1, 3);
		addEdge(graph, 1, 8);
		
		addEdge(graph, 2, 1);
		addEdge(graph, 2, 7);
		
		addEdge(graph, 3, 1);
		addEdge(graph, 3, 4);
		addEdge(graph, 3, 5);
		
		addEdge(graph, 4, 3);
		addEdge(graph, 4, 5);
		
		addEdge(graph, 5, 3);
		addEdge(graph, 5, 4);
		
		addEdge(graph, 6, 7);
		
		addEdge(graph, 7, 2);
		addEdge(graph, 7, 6);
		addEdge(graph, 7, 8);
		
		addEdge(graph, 8, 1);
		addEdge(graph, 8, 7);
		
		//DFS (깊이 우선 탐색) 
		dfs(1);

	}
}

B. 스택으로 구현  

import java.util.LinkedList;
import java.util.Stack;

public class DFS_stack {

	public static boolean[] visited = new boolean[9]; //방문 처리를 위한 배열 
	public static LinkedList<LinkedList<Integer>> graph = new LinkedList<LinkedList<Integer>>(); //그래프 
	
	
	//그래프 간선 추가 (단방향 그래프) 
	public static void addEdge(LinkedList<LinkedList<Integer>> graph, int u, int v) {
		graph.get(u).add(v);
	}
	
	//DFS - 스택으로 구현 
	public static void dfs(int startVertex) {
		Stack<Integer> st = new Stack<>(); //스택 생성 
		
		st.push(startVertex); //시작 정점 스택 삽입 
		
		while(!st.isEmpty()) {
			startVertex = st.pop(); //스택의 최상단 노드 반환(LIFO)
			if(!visited[startVertex]) { //해당 정점이 방문되지 않았다면 
				visited[startVertex] = true; //방문 체크 
				System.out.print(startVertex + " ");
				for(int vertex : graph.get(startVertex)) //인접 정점 중에서 
					if(!visited[vertex]) st.push(vertex); //방문하지 않은 정점을 스택에 삽입 
			}
		}
	}
	
	public static void main(String[] args) {
		
		//그래프 초기화
		for(int i = 0; i < 9; i++)
			graph.add(new LinkedList<Integer>()); //각 정점의 연결 리스트 생성 
		
		//그래프 간선 추가 
		addEdge(graph, 1, 2);
		addEdge(graph, 1, 3);
		addEdge(graph, 1, 8);
		
		addEdge(graph, 2, 1);
		addEdge(graph, 2, 7);
		
		addEdge(graph, 3, 1);
		addEdge(graph, 3, 4);
		addEdge(graph, 3, 5);
		
		addEdge(graph, 4, 3);
		addEdge(graph, 4, 5);
		
		addEdge(graph, 5, 3);
		addEdge(graph, 5, 4);
		
		addEdge(graph, 6, 7);
		
		addEdge(graph, 7, 2);
		addEdge(graph, 7, 6);
		addEdge(graph, 7, 8);
		
		addEdge(graph, 8, 1);
		addEdge(graph, 8, 7);
		
		
		
		//DFS (깊이 우선 탐색) 
		dfs(1);

	}

}

---

BFS(Breadth First Search)

'너비 우선 탐색'이라는 의미를 가지고, 가까운 노드부터 탐색하는 알고리즘임

사용 자료구조 : 큐 (선입선출 방식) → 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색 진행하게 됨

동작 과정 :

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리함
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리함
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함

—> 탐색 순서 : 큐에 들어간 순서(큐는 선입선출 구조 이니까 큐에 들어간 순서가 곧 방문 순서)

 

구현방식

import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static boolean[] visited = new boolean[9];
	public static LinkedList<LinkedList<Integer>> graph = new LinkedList<LinkedList<Integer>>();
	
	public static void addEdge(LinkedList<LinkedList<Integer>> graph, int u, int v) {
		graph.get(u).add(v);
	}
	
	//BFS 정의 
	public static void bfs(int startVertex) {
		Queue<Integer> q = new LinkedList<>(); //큐 선언 
		
		q.offer(startVertex); //시작 노드 큐에 삽입 
		visited[startVertex] = true; //시작 노드 방문 처리 
		
		//빈 큐가 될 때까지 반복
		while(!q.isEmpty()) {
			int vertex = q.poll(); //dequeue 
			System.out.print(vertex + " ");
			
			//해당 정점과 인접하지만 아직 방문하지 않은 원소들을 큐에 삽입
			for(int v : graph.get(vertex))
				if(!visited[v]) {
					q.offer(v); //enqueue 
					visited[v] = true;
				}
		}
	}
	
	public static void main(String[] args) {
		//그래프 초기화 
		for(int i = 0; i < 9; i++)
			graph.add(new LinkedList<Integer>());
		 
		//그래프 간선 추가 
		addEdge(graph, 1, 2);
		addEdge(graph, 1, 3);
		addEdge(graph, 1, 8);
			
		addEdge(graph, 2, 1);
		addEdge(graph, 2, 7);
				
		addEdge(graph, 3, 1);
		addEdge(graph, 3, 4);
		addEdge(graph, 3, 5);
				
		addEdge(graph, 4, 3);
		addEdge(graph, 4, 5);
				
		addEdge(graph, 5, 3);
		addEdge(graph, 5, 4);
				
		addEdge(graph, 6, 7);
				
		addEdge(graph, 7, 2);
		addEdge(graph, 7, 6);
		addEdge(graph, 7, 8);
				
		addEdge(graph, 8, 1);
		addEdge(graph, 8, 7);
				
		//BFS (넓이 우선 탐색) 
		bfs(1);
	}
}

---

추가)

2차원 배열에서의 탐색 문제의 경우 —> 그래프 형태로 바꿔서 생각해보자!

2차원 배열에서의 (row, col) 좌표 = 그래프의 정점

2차원 배열에서의 상하좌우 인접 좌표 = 그래프에서 간선으로 연결된 정점들

 

 

참고) '이것이 취업을 위한 코딩테스트다' 책