그래프 탐색 알고리즘( Graph Search Algorithm )

📋 목 차

❓ 그래프 탐색

Depth-First Search( DFS )

Breadth-First Search ( BFS )

---

 

❓ 그래프 탐색 

그래프 탐색 문제란? 어떤 한 그래프의 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Vertex, V)들을 모두 찾아야 하는 문제를 의미합니다.
그래프 탐색 알고리즘 (Graph Search Algorithm)에는 흔히 너비 우선 탐색( Breadth-First Search, BFS)과 깊이 우선 탐색(Depth-First Search, DFS)이 있습니다.

 

🔶 Depth-First Search

DFS 요약

-그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
-루트 노드(or 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
-스택 자료구조를 기초

깊이 우선 탐색이라고 불리는 이유는 그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하기 때문입니다.

알고리즘 개요는 시작점 → 시작점에 연결된 정점 → 시작점에 연결된 정점에 연결된 정점~ 식으로 재귀 혹은 스택 통해 탐색을 수행하고 더 이상 연결된 간선이 없을 때까지 탐색하면 다시 되돌아가 연결된 정점을 탐색하면 됩니다.

시간복잡도는 인접 행렬로 구현하느냐, 인접 리스트로 구현 하느냐에 따라서 다른데, 아래와 같습니다.

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

 

메모리 측면에서 보면, 인접 행렬 방식은 모든 관계를 저장하므로 정점(노드)갯수가 많을수록, 메모리가 불필요하게 낭비됩니다. 반면, 인접 리스트 방식은 연결된 정보 만을 저장하기 때문에 메모리를 효율적으로 사용합니다.

즉, 메모리 효율 : 인접 리스트 > 인접 행렬

속도 측면에서 보면, 인접 행렬 방식은 graph[1][2]와 같이 바로 확인이 가능하지만, 인접 리스트는 노드에 대한 인접 리스트를 차례로 수행하여야 하므로 정보를 얻는 속도가 느립니다.

즉, 조회 속도 : 인접 리스트 < 인접 행렬

그러므로 특정 노드와 연결된 모든 인접 노드를 순회 해야 할 때는 인접 리스트 방식이 메모리 공간 낭비가 적습니다.

스택 자료 구조를 이용한 DFS의 구체적인 동작 과정은 다음과 같습니다.

1. 시작점인 1번 노드를 스택에 넣고 방문 처리
2. 스택 최상단 노드(1번)와 미방문한 노드 중 가장 번호가 낮은 2번 넣고 방문 처리
3. 스택 최상단 노드(2번)와 미방문한 노드(7번)를 스택에 넣고 방문 처리
4. 스택 최상단 노드(7번)와 미방문한 노드 중 가장 번호가 낮은 6번 넣고 방문 처리
5. 스택 최상단 노드(6번)와 미방문한 노드가 없을 때는 추출(pop)
6. 스택 최상단 노드(7번)와 미방문한 노드(8번)를 스택에 넣고 방문처리
7. 이와 같은 메커니즘으로 스택에 아무것도 없을 때까지 반복

1) 재귀함수(Recursive Function)

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미합니다. 이를 작성할 때에는 반드시 종료 조건을 만들어서 함수를 작성해야합니다. 만약 종료 조건을 제대로 명시하지 않으면, 함수가 무한이 호출되기 때문입니다.

(1) 재귀함수 응용 : 유클리드 호제법

유클리드 호제법은 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다.

기본개념은 두 개의 A, B가 존재하고, A를 B로 나눈 나머지를 C라고 하겠습니다. ( A > B )

이 때, A와 B의 최대공약수는 B와 C의 최대공약수와 같습니다. (증명을 찾아봐야 한다.)

이러한 성질을 이용해서 계속적으로 나눗셈을 진행해서 C가 0이 되었을 때, 즉 나머지가 0이 되었을 때의 나누는 수가 최대공약수가 됩니다.

🔶 Java로 구현한 유클리드 호제법

/**
     * 유클리드 호제법 구현 메서드
     * @param bn : 큰 숫자
     * @param sn : 작은 숫자
     * @return
     * 큰 숫자를 작은숫자로 나눈 값이 0이면 작은숫자 리턴, 아니면 재귀형태로 자신을 호출
     */
    public int eucd(int bn, int sn) {
        // 큰숫자를 작은숫자로 나눈 나머지를 계산
        int r = bn % sn;
        // 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
        if (r == 0) {
            return sn;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자와 나머지를 넣어줌
            return eucd(sn, r);
        }
    }

예시)

72, 42 두 개의 수로 유클리드 호제법을 사용해서 최대공약수를 구해보겠습니다.

1. 먼저 두개의 수 중 큰 수를 찾습니다. 여기서는 72입니다.
2. 큰 수를 작은 수로 나눠서 나머지를 구합니다. => 72 % 42 = 30(나머지)
3. 나머지를 가지고 앞에서 나눈 수를 다시 나눠서 나머지를 구합니다. => 42 % 30 = 12(나머지)
4. 3번의 과정을 반복합니다. => 30 % 12 = 6(나머지)
5. 3번의 과정을 반복합니다. => 12 % 6 = 0(나머지)
6. 5번의 과정을 마지막으로 나머지가 0이 되었으므로 그 시점에 나눈 수가 최대공약수가 됩니다.
7. 위의 순서대로라면 72와 42의 최대공약수는 6이 됩니다.

 

🔶 Breadth-First Search

BFS 요약

- 너비우선탐색
- 가까운 노드부터 탐색하는 알고리즘
- 큐 자료구조에 기초한다.
- 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

BFS는 그래프의 시작점에서 (너비가) 가까운 점들부터 우선적으로 탐색하기 때문입니다.

알고리즘 개요는 시작점을 큐(Queue)에 넣은 뒤에 큐에 아무런 요소가 없을 때까지 인접한 정점들을 탐색해 나아가면 진행됩니다.

이 때 인접한 정점들을 보는 과정은, 그래프를 인접 행렬로 저장하면 O(V^2), 인접 리스트로 저장하면 O(V+E)이 됩니다.

시간 복잡도

• 인접 행렬 : O(v^2)
• 인접 리스트 : O(V+E)

큐를 이용한 BFS의 구체적인 동작과정은 다음과 같습니다.

1. 시작점인 1을 큐에 넣고 방문처리를 한다.
2. 1을 꺼내고 인접한 정점인 2,3,8을 큐에 넣고 방문처리를 한다.
3. 큐에 2를 꺼내고 방문하지 않은 7을 꺼내서 방문처리
4. 큐에서 3을 꺼내고 방문하지 않은 4,5를 꺼내서 방문처리
5. 위와 같이 큐에서 더 이상 꺼낼 것이 없을 때까지 반복

 

❓ 너비우선탐색을 할 때 다른 자료구조도 아닌 굳이 큐(Queue) 자료구조를 이용하는 것일까?

먼저 탐색되는 위치를 먼저 빼내서 인접한 점들을 본다는 요구 사항 때문입니다.

이러한 요구사항을 지원하는 가장 간단하고 빠르고 컴팩트한 자료구조가 큐(Queue)이기 때문입니다.

❓ FIFO를 리스트로 구현하는 게 아니라 deque를 사용하는 이유?

deque에서 원소를 삽입할 때는 .append(N)를 사용하고, 원소를 뺄 때는 .popleft(), 원소를 역순으로 바꾸고자 할 때는 .reverse()를 사용합니다.

그러나 리스트를 이용해서 특정 인덱스의 원소를 삭제하기위해 .pop를 사용한다면, 원소를 꺼내고 위치를 조정하는 O(k) 만큼 시간복잡도가 더 필요하기 때문에 list가 아닌 deque를 사용합니다.

🔶 ‘최단거리’ 문제에서 너비우선탐색(BFS) 사용하기

BFS가 빛을 발하는 경우는 그래프의 간선의 가중치가 모두 동일할 때 나타납니다. 이 때, 시작점에서 모든 점까지의 최단 거리는 달리 말하면 필요한 최소 간선(Edge) 개수로 표현이 가능합니다.

BFS는 시작점에서 가까운 점들부터 탐색이 되기 때문에 탐색하는 과정에서 사용되는 간선의 개수를 체크해 나아가면 그래프의 전선의 가중치가 모두 동일한 경우 최단 거리를 O(V+E)에 구할 수 있습니다.