[알고리즘] DFS & BFS

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

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

해당 그래프를 완벽하게 탐색

스택 자료구조(or 재귀 함수) 사용

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

출처 : https://developer-mac.tistory.com/64

 

DFS 구현

public static boolean[] visited = new boolean[9];	//방문 처리 배열
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();	//그래프를 표현하는 인접리스트

public static void dfs(int x) {
    visited[x] = true;  //현재 노드를 방문처리
    System.out.print(x + " ");

    //현재 노드(x)와 연결된 다른 노드들을 재귀적으로 방문
    for (int i = 0; i < graph.get(x).size(); i++) {
        int n = graph.get(x).get(i);
        if (!visited[n]) {  //방문하지 않은 노드라면 방문
            dfs(n);
        }
    }
}

 

 

---

 

 

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

가까운 노드부터 우선적으로 탐색하는 알고리즘

두 노드 사의 최단 경로를 탐색

큐 자료구조 사용

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

출처 : https://developer-mac.tistory.com/64

 

BFS 구현

public static boolean[] visited = new boolean[9];	//방문 처리 배열
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();	//그래프를 표현하는 인접리스트


public static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);     //큐에 현재 노드를 삽입
    visited[start] = true;  //현재 노드를 방문 처리

    while (!q.isEmpty()) {
        int x = q.poll();   //큐에서 현재 노드 꺼냄
        System.out.print(x + " ");

        for (int i = 0; i < graph.get(x).size(); i++) {
            int n = graph.get(x).get(i);
            if (!visited[n]) {  //방문하지 않은 노드들을 큐에 삽입하고 방문처리
                q.offer(n);
                visited[n] = true;
            }
        }
    }
}

 

 

 

 

DFS / BFS 구현 문제

https://www.acmicpc.net/problem/1260

풀이 : https://yemi-devlog.tistory.com/entry/백준Java-1260-DFS와-BFS

 

 

 

---

[참고]

- 이것이 취업을 위한 코딩테스트다 with 파이썬

- https://developer-mac.tistory.com/64