[이코테] 탐색 알고리즘 DFS/BFS

 

DFS

- 깊이 우선 탐색(Depth-First Search). 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘.

- 스택(혹은 재귀함수) 이용

 

먼저 재귀적으로 구현한 DFS는 다음과 같다.

package codingTest;

public class DFS {

    static void dfsGraph(int graph[][], int num, boolean visited[]) {
		
        // num 노드를 방문 처리
        visited[num] = true;
        // 방문한 노드 프린트
        System.out.println(num);
		
        // 이중배열에서 graph[num]의 길이만큼 for문을 돌림.
        for(int i=0; i<graph[num].length; i++) {
        	// 배열 안에 있는 각 값을 tmp에 담음.
            int tmp = graph[num][i];
            // 작은 순서대로 배열 안에 넣어져 있기 때문에 비교할 필요 없음.
            
            // 만약 방문하지 않았다면?
            if(!visited[tmp]) {
            	// 먼저 방문
                visited[tmp] = true;
                
                // 재귀
                dfsGraph(graph, tmp, visited);
            }
        }
    }

    public static void main(String[] args) {

		// 그래프의 연결 상태
        int graph[][] = {{},{2,3,8}, {1,7}, {1,4,5}, {3,5},{3,4},{7},{2,6,8},{1,7}};
        
        // 방문했는지 true/false로 구분
        boolean visited[] = new boolean[n+1];
		
        //재귀함수
        dfsGraph(graph, 1, visited);
    }
}

1 - 2 - 7 - 6 - 8 - 3 - 4 - 5  순으로 들어가는 것이 맞고 콘솔 창에 결과를 보면 다음과 같았다. 

잘 방문한 것을 확인할 수 있었다.

 

 

BFS

- (Breadth First Search) 너비 우선 탐색 : 가까운 노드부터 탐색하는 알고리즘 

- 큐를 사용 

 

num을 잘못 잡아서 엄청 헤맸는데 다시 생각해보니까 잘 되었다. 

package codingTest;

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

public class BFS {
    public static void bfsGraph(int graph[][], boolean visited[], int num) {
        Queue<Integer> q = new LinkedList<>();
        // 큐에 처음 num 값을 삽입.
        q.offer(num);
        visited[num] = true;
		
        
        // 큐가 empty 아닐 때 까지 반복
        while(!q.isEmpty()) {
            // 큐에서 꺼냄.
            int tmp = q.poll();
            System.out.println(tmp);
			// 꺼낸 노드와 인접한 노드를 하나씩 확인.
            for (int i = 0; i < graph[tmp].length; i++) {
                // 인접한 노드
                int temp = graph[tmp][i];
                // 노드를 방문하지 않았으면
                if(!visited[temp]) {
                	// 큐에 하나씩 넣고 방문 처리
                    q.offer(temp);
                    visited[temp] = true;
                }
            }
        }

    }

    public static void main(String[] args) {

        int graph[][] = {{},{2,3,8}, {1,7}, {1,4,5}, {3,5},{3,4},{7},{2,6,8},{1,7}};
        boolean visited[] = new boolean[9];

        bfsGraph(graph, visited, 1);

    }
}

1 - 2 - 3 - 8 - 7 - 4 - 5 - 6

 

콘솔에 찍힌 결과를 보면 다음과 같다.