[알고리즘] DFS/BFS 📌

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

• 한 노드에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법
• 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다

 

 

 

DFS의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다 : 재귀 or 스택
• DFS를 구현할 때 노드의 방문 여부를 반드시 검사해야 한다
  • 검사하지 않을 경우 무한 루프에 빠질 수 있다
  • ex) visit[index] = true;
• 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가, 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다
• 모든 노드를 방문하고자 할 떄, DFS를 사용한다
• BFS(너비 우선 탐색)보다 더 간단하다
• 검색 속도 자체는 BFS에 비해 느리다

 

 

 

DFS의 탐색 과정

 

 

 

 

DFS 구현 코드 - JAVA

// DFS, 재귀, 인접행렬
// i 정점부터 시작한다
public static void dfs(int i) {
	visit[i] = true;
    
    for(int j=1;j<=n;j++) {
    	if(map[i][j] == 1 && visit[j] == false) {
        	dfs(j);
        }
    }
}

 

 

 

 

---

BFS (Breadth-First Search)

• 한 노드에서 시작한 인접 노드를 먼저 탐색하는 방법이다

 

 

BFS의 특징

• BFS는 재귀적으로 동작하지 않는다
• BFS 알고리즘도 DFS와 마찬가지로 각 노드의 방문 여부를 검사해야 한다
• BFS는 방문한 노드를 차례대로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다
• 즉, 선입선출(FIFO) 원칙으로 탐색한다
• 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다
• 깊게 탐색하기 전에 넓게 탐색하는 것이다
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다
  • ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후, A와 B 사이에 존재하는 경로를 찾는 경우
  • DFS - 모든 친구 관계를 다 확인해야 할 수도 있다
  • BFS - A와 가까운 관계부터 탐색한다

 

 

 

BFS의 탐색 과정

깊이가 1인 모든 노드를 방문하고 난 후, 깊이가 2인 모든 노드를 방문하고, 그 다음에 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다

 

 

 

 

 

BFS 구현 코드 - JAVA

// bfs, Queue 사용, 인접행렬, i 정점부터 시작한다
public static void bfs(int i) {
	Queue<Integer> q = new LinkedList<>();
    q.offer(i);
    visit[i] = true;
    
    while(!q.isEmpty()) {
    	int temp = q.poll();
        
        for(int j=1;j<=n;j++) {
        	if(map[temp][j] == 1 && visit[j] == false) {
            	q.offer(j);
                visit[j] = true;
            }
       	}
    }
}

 

 

 

 

 

---

💡 DFS vs BFS

dfs는 깊게 탐색, bfs는 넓게 탐색한다

 

 

---

참고)

https://bbangson.tistory.com/42

[Java] DFS, BFS 정리