알고리즘 - (2) BFS / DFS

hznnoy·2025년 9월 14일

CS

목록 보기

12/24

BFS (Breadth First Search 너비 우선 탐색)

그래프와 가까운 노드부터 탐색하는 알고리즘
루트 노드와 같은 거리에 있는 노드를 우선으로 방문하며 탐색한다.

최단경로 혹은 임의의 경로를 찾고자 할 때 사용
큐를 이용하여 구현

탐색 방식

시작 노드를 큐에 넣는다

큐에서 시작 노드를 꺼내고, 인접한 노드인 2, 3, 4번 노드를 큐에 넣는다

큐에서 2번 노드를 꺼내고, 인접한 노드인 5, 6번 노드를 큐에 넣는다

큐에서 3번 노드를 꺼내고, 인접한 노드인 7번 노드를 큐에 넣는다

큐에서 4번 노드를 꺼내고, 인접한 노드인 8, 9번 노드를 큐에 넣는다

큐가 빌 때까지 위의 과정을 반복한다.

예시 코드

static boolean[] visit; 
// 인접리스트, 인접행렬 중 요구사항에 따라 선택
static LinkedList<Integer>[] graph;
static int[][] graph; 

public static void bfs(int start){
	Queue<Integer> q = new LinkedList<();
	q.add(start); // 시작 노드를 큐에 넣는다
	visit[start] = true; // 노드의 방문 여부 체크
	
	while(!q.isEmpty()){
		int temp = q.poll(); // 큐에서 노드를 꺼낸다
		
		for(int i=0; i<graph[start]; i++){
			int next = graph[start][i]; // 인접한 노드들을 체크
			if(!visit[next]){ // 방문한 적 없는 노드일 경우 큐에 넣고, 방문 처리
				q.add(next);
				visit[next]=true;
			}
		}
	}
}

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

그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘.
갈 수 있는 한 끝까지 탐색하고, 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문한다.

모든 노드를 방문하고자 할 때 사용
스택이나 재귀를 이용하여 구현할 수 있음

탐색 방식

시작 노드를 스택에 넣는다.

스택에서 1번 노드를 꺼내고, 1번 노드가 갈 수 있는 7, 5, 2번 노드를 스택에 넣는다.

스택에서 2번 노드를 꺼내고, 2번 노드가 갈 수 있는 4, 3번 노드를 스택에 넣는다.

스택에서 3번 노드를 꺼내고, 3번 노드는 더 이상 갈 수 있는 노드가 없으므로 추가하지 않는다.

스택에서 4번 노드를 꺼내고, 3번 노드는 더 이상 갈 수 있는 노드가 없으므로 추가하지 않는다.

스택에서 5번 노드를 꺼내고, 5번 노드가 갈 수 있는 6번 노드를 스택에 넣는다.

스택이 빌 때까지 위의 과정을 반복한다.

->
탐색 방식을 잘 보면, 하위 노드를 모두 방문하면 부모 노드로 돌아간다는 특징이 있음 = 재귀

예시 코드

static boolean[] visit;
// 인접리스트, 인접행렬 중 요구사항에 따라 선택
static LinkedList<Integer>[] graph;
static int[][] graph; 

public static void dfs(int start){
	visit[start] = true; // 시작 노드 방문 처리
	
	for(int i=0; i<graph[start]; i++){
		int next = graph[start][i]; // 갈 수 있는 다음 노드 탐색
		if(!visit[next]){ // 방문 여부 확인
			dfs(next); // 재귀 형태로 구현
		}
	}
}

BFS와 DFS의 비교

	BFS	DFS
탐색 과정	현재 정점에 연결된 가까운 점들부터 탐색	현재 정점에서 갈 수 있는 끝까지 방문하며 탐색
구현 방법	큐	스택 or 재귀함수
활용	최단 경로를 찾고자 할 때	모든 노드를 방문하고자 할 때 사이클(순환)의 존재 여부를 확인할 때