[알고리즘] BFS / DFS 접근 방식 정리

DFS / BFS 알고리즘의 특징은 이전 글에서 정리한 적 있다.

코테 준비를 하면서, 어떤 유형에서 어떤 알고리즘을 써야할지 헷갈리는 부분이 많아 정리해보려고 한다.

 

---

 

 

DFS

일반적으로 재귀함수를 이용하여 구현한다. 

 

1. 정점 v를 방문한다.
2. 정점 v에서 인접한 정점 중에 방문하지 않은 정점 w가 있다면 w를 v로 하여 1부터 재귀함수를 반복한다.
3. 인접한 정점을 모두 방문했다면 스택에서 정점을 꺼내 위를 반복한다. 

 

import java.util.LinkedList;

public class DFS_Graph {

    private int V;
    private LinkedList<Integer> adj[];

    DFS_Graph(int v){
        V = v;
        adj = new LinkedList[v];
        // v개의 LinkedList 선언 및 생성
        for (int i=0; i<v; ++i){
            adj[i]= new LinkedList();
        }
    }

    // 간선 추가
    void addEdge(int v, int w){
        adj[v].add(w);
    }

    void DFS(int v){
        boolean visited[] = new boolean[V]; // 각 노드의 방문 여부 저장
        recursiveDFS(v, visited);
    }

    void recursiveDFS(int v, boolean visited[]){
        // 현재 노드를 방문한 것으로 체크
        visited[v] = true;
        for (int n : adj[v]){
            if (!visited[n]){
                // 방문하지 않은 노드라면 재귀 호출
                recursiveDFS(n, visited);
            }
        }
    }
}

 

 

1) 연결된 그래프를 완전 탐색하는 데 활용 가능

2) 모든 조합의 경우의 수를 알아야 할 경우 (조합, 순열 모든 경우의 수를 하나하나 다 찾고자 할 때)

 

 

---

BFS 

일반적으로 Queue를 이용하여 구현한다. 

 

1. 정점 v를 방문한다.
2. 정점 v에 인접한 정점 중 방문하지 않은 정점을 차례로 방문하면서 큐에 넣는다.
3. 인접한 정점 모두 방문했다면 deque하여 받은 값 정점 v로 설정하고 2번을 반복한다.
4. 큐가 공백이라면 탐색 완료 한것이다.

import java.util.LinkedList;

public class BFS_Graph {
    private int V;
    private LinkedList<Integer> adj[];

    BFS_Graph (int v){
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; i++){
            adj[i] = new LinkedList<>();
        }
    }

    // 간선 추가
    void addEdge(int v, int w){
        adj[v].add(w);
    }

    void BFS(int s){
        boolean visited[] = new boolean[V];
        //LinkedList는 Queue의 기능을 함
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (!queue.isEmpty()){
            // 큐에서 노드 추출 및 출력
            s = queue.poll();
            System.out.println(s + " ");
            // s랑 연결된 애들 다 불러오기
            for (int n : adj[s]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

 

 

1) 연결된 그래프를 완전 탐색하는 데 활용 가능

2) depth(길이)를 계산해야 되는 문제에 활용 

3) 가중치가 같은 그래프에서 최단거리를 찾는데 활용

 

---

 

 

DFS, BFS 문제는 주로 그래프 순회 문제, 길찾기 문제에서 사용된다.

 

1. 그래프 순회

그래프 순회는 노드를 하나씩 방문하여 그래프를 탐색하는 문제이다.

• 노드 연결  : 1번 ~ N번까지 도달 가능한지, 경로를 판단한다.
• 노트 방문 순서를 출력 : 각 노드를 어떤 순서로 방문하는지 출력한다.

2. 길찾기

주로 0과 1로 이루어진 2차원 배열이 주어지며, 0은 벽, 1은 길을 의미한다.

• 도달 여부 판단 : 시작 위치부터 목표 위치까지 도달 가능한지 여부를 판단한다.
• 군집 개수 세기  : 1로 연결된 영역이 몇 개 존재하는지 파악하는 문제이다. ('단지 수 세기', '섬 개수')
• 최단 거리 계산 : 특정 지점에서 목표 지점까지 가장 빠르게 이동할 수 있는 거리를 구하는 문제이다.

1) BFS / DFS 둘다 사용해도 무관한 경우

2) DFS를 사용하는 것이 압도적으로 편리한 경우

3) BFS를 사용하는 것이 압도적으로 편리한 경우

 

로 나눌 수 있다.

 

단순히 "모든 노드를 방문해야 하는 문제" 혹은 "연결되어 있는 덩어리를 찾는 문제" 는, 성능 차이가 얼마 없으므로 구현하기 편한 것을 선택한다.

대표 유형으로 '단지 번호 붙이기', '섬의 개수', '바이러스 감염된 컴퓨터 수' 등이나

단순 연결 여부를 확인하는 문제는

보통 DFS가 재귀함수를 이용해 코드가 더 간결하게 짜여서 선호되는 경향이 있다.

 

 

 

---

정리

 

 

DFS를 사용하는 것이 편리한 경우

대표적으로,

1. 경로의 특징을 저장해야 하는 문제
2. 백트래킹 (해가 아니라면 다시 돌아옴)
3. 사이클 찾기 

 

모든 경우의 수, 조합, 순열 혹은 경로의 특징을 물을 경우 -> DFS 

 

 

 

 

BFS를 사용하는 것이 편리한 경우

'최단거리' 는 무조건 BFS 라고 기억해도 된다.

1. 가중치 없는 그래프의 최단 거리
2. 동시 출발 (확산) 문제

 

최단거리, 최소횟수, 동시에 퍼지는 것 ->  BFS