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

그래프 탐색 문제

그래프 탐색 문제란? 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을때, 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Vertex, V)들을 모두 찾아야 하는 문제를 의미합니다.

이 문제를 해결하는 그래프 탐색 알고리즘에는 흔히 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있습니다.
이에 대해서 알아보도록 합시다.

두 알고리즘의 공통점은 그래프 탐색 문제에 대한 해답을 올바르게 찾는다는 점이다.
각 알고리즘의 특성을 살펴보자.

1. 깊이우선탐색(Depth-First Search, DFS)

DFS는 깊이 우선 탐색이라고 불리며 그 이유는 그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하기 때문입니다.
알고리즘 개요는 시작점-> 시작점에 연결된 정점->시작점에 연결된 정점에 연결된 정점~~ 식으로 재귀 혹은 스택 통해 탐색을 수행하고 더 이상 연결된 간선이 없을때까지 탐색하면 다시 되돌아가 연결된 정점을 탐색하면됩니다.
시간복잡도는 인접행렬로 구현하느냐, 인접리스트로 구현하느냐에 따라서 다른데, 아래와 같다.

• 인접 행렬: 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)

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

이러한 특성때문에 DFS를 구현하는데 재귀함수를 쓴다.

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

• 두 자연수 A,B에 대해서 A를 B로 나눈 나머지를 R이라고 할때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

Step	최대공약수(A,B)	A	B	A%B
1	gcd(192, 162)	192	162	30
2	gcd(162, 30)	162	30	12
3	gcd(30, 12)	30	12	6
4	gcd(12, 6)	12	6	0

즉, 유클리드 호제법에 의하여 A%B가 0이되는 순간 B의 값 6이 최대공배수가 된다.

이를 파이썬 코드로 표현해보자.

def gcd(a, b):
    if a % b == 1: return 1
    if a % b == 0: return b
    return gcd(b, a % b)
gcd = gcd(a, b)
lcm = (a * b) // gcd
print(gcd)
print(lcm)

참고: 백준 연습문제 링크 최대공약수와 최소공배수

2. 너비우선탐색(Breadth-First Search, BFS)

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. 위와 같이 큐에서 더이상 꺼낼것이 없을때까지 반복

1) 큐(queue) 자료구조?

어떠한 자료(data)가 위 그림처럼 왼쪽으로 들어와서 오른쪽으로 나가는 자료구조를 의미한다.
먼저 들어온것이 먼저 나가는 구조를 FIFO(First In First Out)구조라고 하며 이를 지원하는 가장 간단하고 빠르며 컴팩트한 자료구조를 큐(Queue)이다. python에서는 이를 구현하기 위해서 deque 라이브러리를 이용해서 구현한다.

2) 그럼 왜 너비우선탐색을 할때 다른 자료구조도 아니고 굳이 큐(queue) 자료구조를 이용하는것일까?

탐색되는 점들을 저장하는 자료구조로 큐(queue)를 이용하는 이유는 먼저 탐색되는 위치를 먼저 빼내서 인접한 점들을 본다는 요구 사항 때문이다.
이러한 요구 사항은 FIFO(First In First Out) 라고 불리며, 이를 지원하는 가장 간단하고 빠르고 컴팩트한 자료구조가 큐(queue)이기 때문이다.

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

위 질문과 일맥상통하는 질문이다. deque에서 원소를 삽입할때는 .append(N)를 사용하고, 원소를 뺄때는 .popleft(),원소를 역순으로 바꾸고자 할때는 .reverse()를 사용한다.
그러나 리스트를 이용해서 특정 인덱스의 원소를 삭제하기위해 .pop를 사용한다면, 원소를 꺼내고 위치를 조정하는 O(k) 만큼 시간복잡도가 더 필요하기 때문에 list가 아닌 deque를 사용한다.

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

BFS가 빛을 발하는 경우는 그래프의 간선의 가중치가 모두 동일할 때 나타납니다. 이 때, 시작점에서 모든 점까지의 최단 거리는 달리 말하면 필요한 최소 간선(Edge) 개수로 표현이 가능합니다. BFS는 시작점에서 가까운 점들부터 탐색이 되기 때문에 탐색하는 과정에서 사용되는 간선의 개수를 체크해 나아가면 그래프의 간선의 가중치가 모두 동일한 경우 최단 거리를 O(V+E)에 구할수 있습니다.

그래프 면접 예상 질문

1) 최단거리는 bfs로 왜 구하는가?
2) 간선의 가중치가 모두 다르면?
3) 간선의 가중치가 만약 음수가 나오면?
4) 무방향 그래프에서 컴포넌트는 뭘 하는 건가요?
5) 무방향 그래프에서 컴포넌트는 왜 구하는 건가요?

인접리스트 방식: 각 노드가 연결된 정보를 표현(2차원리스트) 일반적으로 0번은 빈 걸로 냅누는게 낫다. 왜냐면 문제에서 0번보다는 1번이라고 해서

vistited: 각 노드가 방문된 정보를 표현 (1차원 리스트)

문제 이름	문제 링크	답안 코드 링크
DFS와 BFS	링크	링크
단지번호붙이기	링크	링크
물통	링크	링크
연구소	링크	링크
미로 탐색	링크	링크
숨바꼭질	링크	링크
탈출	링크	링크
연습문제
유기농 배추	링크	링크
연결 요소의 개수	링크	링크
섬의 개수	링크	링크
양	링크	링크
바이러스	링크	링크
경로 찾기	링크	링크
트리의 부모 찾기	링크	링크
나이트의 이동	링크	링크
촌수계산	링크	링크
현명한 나이트	링크	링크
케빈 베이컨의 6단계 법칙	링크	링크
결혼식	링크	링크
토마토	링크	링크