그래프의 탐색(깊이 우선 탐색과 너비 우선탐색)

그래프의 탐색

---

그래프를 탐색한다는 것은 그래프의 정점들을 탐색한다는 의미이다.

이때 정점을 탐색하는 순서가 중요한데 크게 두 가지로 나눌 수 있다.

 

바로 깊이 우선 탐색과 너비 우선 탐색이다.

 

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

말 그대로 깊이를 우선적으로 탐색한다.

한 정점을 기준으로 더 이상 탐색할 정점이 없을 때까지 가보고 없으면 최근에 방문했던 노드로 되돌아가 다음 가지 않은 노드를 방문한다.

 

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

말 그대로 너비를 우선적으로 탐색한다.

한 정점을 기준으로 가장 가까운 정점을 모두 방문하고 다음 정점으로 넘어간다.

그 정점에서 가장 가까운 정점부터 모두 방문한다.

 

지금부터 각각에 대해 자세히 알아보도록 하자.

 

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

---

동작 방식

다음과 같은 그래프가 있다고 해보자.

 

노드 1부터 방문한다.

 

1과 인접한 노드 중 하나를 방문한다. 여기선 2를 방문했다.

 

2와 인접한 노드중 하나를 방문한다. 여기선 5를 방문했다.

 

5에선 더 이상 방문할 노드가 없으므로 2로 돌아간다.

2에서 아직 가지 않은 4를 방문한다.

 

4에선 더 이상 방문할 노드가 없으므로 다시 2로 돌아간다.

2도 방문할 노드가 없으므로 1로 돌아간다.

1에서 아직 가지 않은 3을 방문한다.

 

모든 노드를 방문했다.

최종 방문 순서: 1 - 2 - 5 - 4 - 3

 

깊이 우선 탐색 구현하기

깊이 우선 탐색은 스택을 통해 구현할 수 있다.

스택의 FILO(First In Last Out) 특성이 깊이 우선 탐색 방식과 어울리기 때문이다.

과정은 다음과 같다.

1. 1번 노드를 스택에 넣는다.

2. 스택에서 데이터를 꺼내 해당 노드를 방문처리함과 동시에 인접 노드들 중 방문하지 않은 노드들을 스택에 넣는다.

3. 2번 과정을 모든 노드를 방문할 때 까지 반복한다.

 

그림을 통해 자세히 보도록하자.

 

1. 1번 노드를 스택에 넣는다.

 

2. 스택에서 데이터를 꺼내 해당 노드를 방문처리함과 동시에 인접 노드들 중 방문하지 않은 노드들을 스택에 넣는다.

1이 꺼내졌으므로 1을 방문처리한다.

1과 인접한 2와 3은 아직 방문하지 않았으므로 큐에 넣는다.

 

3. 다시 스택에서 데이터를 꺼내 해당 노드를 방문처리함과 동시에 인접 노드들 중 방문하지 않은 노드들을 스택에 넣는다.

3이 꺼내졌으므로 3을 방문처리한다.

3과 인접한 노드는 없다.

 

4. 다시 스택에서 데이터를 꺼내 해당 노드를 방문처리함과 동시에 인접 노드들 중 방문하지 않은 노드들을 스택에 넣는다.

2가 꺼내졌으므로 2를 방문처리한다.

2와 인접한 5와 4는 아직 방문하지 않았으므로 스택에 넣는다.

 

5. 스택에 남은 4와 5에 대해서도 같은 과정을 수행한다.

4와 5 모두 인접한 노드가 없다.

각각 방문처리만 하면 된다.

 

모든 노드를 방문했다.

최종 방문순서는 1 - 3 - 2 - 4 - 5가 된다.

 

한 가지 이상한 점이 있다.

분명 위와 같은 방식인데 방문순서가 달라졌다. 왜일까?

 

바로 인접한 노드에 대해서 방문한 순서가 달라졌기 때문이다.

1과 인접한 노드 중 2를 먼저 방문하느냐 3을 먼저 방문하느냐에 따라 결과는 달라지고

2와 인접한 노드 중 5를 먼저 방문하느냐 4를 먼저 방문하느냐에 따라 결과는 달라진다.

하지만 이는 크게 신경쓰지 않아도 된다.

중요한 것은 깊이 우선 탐색 방식은 인접한 노드를 하나 정해서 그 노드를 기준으로 계속 내려간다는 것이다.

 

코드는 다음과 같다.

// 그래프 클래스
public static class Graph {

    List<List<Integer>> adjacent;
    int V; // 노드의 갯수

    Graph (int V) {
        adjacent = new ArrayList<>();
        for(int i = 0; i < V; i++) {
            adjacent.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjacent.get(src).add(dest);
    }

}


public static int[] BFS(Graph graph, int start, int n) {
    List<List<Integer>> adjacent = graph.adjacent;
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[n + 1];
    List<Integer> visit_order = new ArrayList<>();


    stack.push(start); // 시작 노드 스택에 넣고 시작하기

    while(!stack.isEmpty()) {
        int node = stack.pop(); // 스택에서 노드 하나 꺼내기


        if(!visited[node]) {
            visited[node] = true; // 해당 노드 방문처리
            visit_order.add(node);
        }


        for(int adjacent_node: adjacent.get(node)) { // 인접한 노드 스택에 넣기
            if(!visited[adjacent_node]) {
                stack.add(adjacent_node);
            }
        }
    }

    return visit_order.stream().mapToInt(i -> i).toArray();
}

public static void solution(int[][] graphInfo, int start, int n) {
    Graph graph = new Graph(n + 1); // 그래프 만들기

    for(int i = 0; i < graphInfo.length; i++) {
        graph.addEdge(graphInfo[i][0], graphInfo[i][1]);
    }

    //깊이 우선 탐색 순회
    int[] DFS_result = DFS(graph, start, n);
    System.out.println("DFS_result = " + Arrays.toString(DFS_result));

}

public static void main(String[] args) {
    solution(new int[][]{{1, 2}, {1, 3}, {2, 5}, {2, 4}}, 1, 5);
}

결과

 

 

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

---

동작 방식

다음과 같은 그래프가 있다고 해보자.

 

노드 1부터 방문한다.

 

1과 인접한 2와 3을 차례로 방문한다.

 

2와 인접한 5와 4를 차례로 방문한다.

 

모든 노드를 방문했다.

최종적인 방문순서: 1 - 2 - 3 - 5 - 4

 

너비 우선 탐색 구현하기

너비 우선 탐색은 큐를 통해 구현할 수 있다.

큐의 FIFO(First In First Out) 특성이 너비 우선 탐색 방식과 어울리기 때문이다.

과정은 다음과 같다.

1. 1번 노드를 큐에 넣고 방문 처리한다.

2. 큐에서 데이터를 꺼낸 다음 해당 데이터와 인접한 노드를 큐에 넣고 방문처리한다.

3. 2번과정을 모든 노드를 방문할 때까지 반복한다.

 

그림을 통해 자세히 보도록하자.

 

1. 1번 노드를 큐에 넣고 방문처리한다.

 

2. 큐에서 데이터를 꺼낸 다음 해당 데이터와 인접한 노드를 큐에 넣고 방문처리한다.

1을 큐에서 꺼낸다.

1과 인접한 2와 3을 큐에 넣고 방문처리한다.

 

3. 다시 큐에서 데이터를 꺼낸 다음 해당 데이터와 인접한 노드를 큐에 넣고 방문처리한다.

2를 큐에서 꺼낸다 

2와 인접한 5와 4를 큐에 넣고 방문처리한다.

 

4. 큐에 남아 있는 데이터들에 대해 위의 과정을 반복한다.

차례대로 3,5,4를 꺼낸다.

모두 인접 노드가 없다.

 

모든 노드를 방문했다.

최종 방문 순서: 1 - 2 - 3 - 5 - 4

 

 

코드는 다음과 같다.

public static class Graph {

    List<List<Integer>> adjacent;
    int V;

    Graph (int V) {
        adjacent = new ArrayList<>();
        for(int i = 0; i < V; i++) {
            adjacent.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjacent.get(src).add(dest);
    }
}

public static int[] BFS(Graph graph, int start, int n) {
    List<List<Integer>> adjacent = graph.adjacent;
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[n + 1];
    List<Integer> visit_order = new ArrayList<>();

    queue.add(start); // 시작 노드 큐에 넣고 시작
    visited[start] = true; // 해당 노드 방문처리
    visit_order.add(start);

    while(!queue.isEmpty()) {
        int node = queue.poll();

        for(int adjacent_node: adjacent.get(node)) {
            if(!visited[adjacent_node]) { // 인접한 노드 큐에 넣고 방문처리
                queue.add(adjacent_node);
                visited[adjacent_node] = true;
                visit_order.add(adjacent_node);
            }
        }
    }

    return visit_order.stream().mapToInt(i -> i).toArray();
}

public static void solution(int[][] graphInfo, int start, int n) {
    Graph graph = new Graph(n + 1); // 그래프 만들기

    for(int i = 0; i < graphInfo.length; i++) {
        graph.addEdge(graphInfo[i][0], graphInfo[i][1]);
    }

    // 너비 우선 탐색 순회
    int[] BFS_result = BFS(graph, start, n);
    System.out.println("BFS_result = " + Arrays.toString(BFS_result));

}

public static void main(String[] args) {
    solution(new int[][]{{1, 2}, {1, 3}, {2, 5}, {2, 4}}, 1, 5);
}

결과

 

 

깊이 우선 탐색이랑 비교했을 때 차이점이 한가지 있다.

바로 방문처리하는 시점이다.

 

깊이 우선 탐색의 경우 스택에서 데이터를 꺼낼 때 해당 데이터를 방문처리했고

너비 우선 탐색의 경우 큐에 데이터를 넣을 때 방문처리 했다.

해당 부분만 유의하면 구현할 때 어려움이 없을 것 같다.

 

 

깊이 우선 탐색과 너비 우선 탐색 활용

---

깊이 우선 탐색 -  백트래킹, 그래프 사이클 감지

 

너비 우선 탐색 -  (무가중치 그래프에서)최단 경로

예시 문제:

[프로그래머스] 게임 맵 최단 거리