[Algorithm] 탐색 알고리즘

탐색 알고리즘

• 미로 탐색 알고리즘
• 다익스트라 알고리즘

 

✅ DFS (Depth First Search)

• '깊이 우선 탐색' 을 뜻한다
• 스택 또는 재귀를 사용한다
• 탐색이 막히면 다시 돌아와 다른 곳을 탐색 할 수 있다 (백트래킹)

 

 

✅ BFS (Breadth First Search)

• '너비 우선 탐색' 을 뜻한다
• 큐(Queue)를 사용한다
• 탐색이 끝난 노드는 큐에서 삭제 (pop) 한다

 

 

✅ BFS 최단 경로

• 위 문제의 포인트는 BFS 탐색으로 (0, 0)을 시작으로 해서 맵의 모든 이동 가능한 경로를 움직일 때 마다 비용을 '1'씩 더해주고 최종 (N,M) 을 만나면 종료하도록 해야함

 

 

✅ 다익스트라 알고리즘 (Dijkstra Algorithm)

• 주어진 시작 지점에서 모든 지점의 최단 경로를 찾는 알고리즘이다. BFS 의 발전형 알고리즘이다
• 음의 가중치가 없는 경우, 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘이다
• 단순 구현은 O(n²) 의 시간복잡도를 갖지만, 우선 순위 큐 사용 시, O(m log n) 의 시간복잡도를 갖는다

 

 

✅ BFS 탐색 vs 다익스트라 알고리즘

정점 V 개, 간선 E개

 

# 용도

• BFS 탐색 : 시작점 → 목표지점 너비우선탐색 수행 (최단 경로를 구할 수 있음)

• 다익스트라 : 시작점 → 나머지 정점 까지의 최단 경로를 구함

 

# 시간복잡도

• BFS 탐색 : E

• 다익스트라 : E log V

 

# 전략

• BFS 탐색 만약 모든 가중치가 '1' 로 동일 할 때

• 다익스트라 가중치가 모두 다를 경우 (단, 양의 가중치)

 

 

✅ 최단 경로 구하기

# 알고리즘 종류

1. Single-Source (one-to-all) : 하나의 출발 노드로부터 다른 모든 노드 까지의 최단 경로 (Dijkstra Algorithm)

2. Single-Destination : 모든 노드로부터 하나의 노드 까지의 최단 경로 (모든 Edge를 뒤집으면 'one-to-all' 과 동일함)

3. Single-Pair (one-to-one) : 하나의 출발 노드로부터 하나의 목적 노드 까지의 최단 경로 (시간복잡도에서 'Single-Source' 보다 안좋음)

4. All-Pair (all-to-all) : 모든 노드 쌍에서 최단 경로 (Floyd Algorithm)

 

# Relax 연산

// u: 정점1 , v: 정점2 w: 정점1과 정점2의 가중치
if(dist[v] > dist[u] + w){
    dist[v] = dist[u] + w;
}

 

• Bellman-Ford Algorithm

  • 모든 Edge에 대해 Relax 연산을 수행 (최대 n-1번)
  • 음수 Edge가 존재할 수 있음
  • O(n∙m)

 

• Dijkstra Algorithm

  • 최단 경로를 계속적으로 갱신하며 탐색
  • 단순 구현 시, O(n²)
  • 우선 순위 큐 사용 시, O(m log n)

 

• Floyd-warshall Algorithm

  • 모든 노드 쌍들간의 최단경로
  • k값을 증가시키며 최단경로 최신화
  • 3중 for문을 사용하기 때문에 O(n³)

 

✅ 우선순위 큐(Priority Queue)

# 정의

• 큐(Queue)와 비슷하지만 내부 구조는 완전히 다르다

• top, pop에서 추출되는 원소는 제일 먼저 들어왔던 게 아닌, 현재 우선순위 큐 안에서 가장 우선순위가 높은 원소이다!!

 

# 구조

priority_queue<T, Container, Compare> pq;

 

# 사용법

insert(element);		// pq에 원소 추가
pop();					// pq에서 top의 원소를 삭제
top();					// top에 있는 원소를 반환

 

# 구현

• Max Heap

priority_queue<int, vector<int>,less<int>> pq;

 

• Min Heap

priority_queue<int, vector<int>,grater<int>> pq;

 

• Custom

typedef pair<int,int> node;

struct cmp {
    bool operator()(node x, node y){
        return x.second > y.second;
    }
};

priority_queue<node, vector<node>, cmp> pq;

 

 

✅ 다익스트라 알고리즘(Dijkstra Algorithm)

# 정의

• 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 방법 (Single Source ans Shortest Path Problem)

 

# Base Logic

• 첫 정점을 기준으로 연결되어 있는 정점을 추가해가며 최단 거리를 갱신함 (정점을 잇기 전까지는 모두 INF)

• A → B 인 경우, Dist[B]는 아래의 2개 중 최소값을 저장한다

  • 시작점부터 A 까지의 최소 비용 + A → B 의 가중치
  • 기존에 가지고 있던 B 의 최소비용

 

먼저 시작점은 E 이다

E 에서 갈 수 있는 경로는 B 와 D 이다

먼저 D 노드를 보면, 현재 비용은 ∞ 이고, E를 거쳐 갈 수 있는 비용은 2 이다. 이 중 최소값은 2이다

B 노드의 경우, 현재 비용은 ∞ 이고, E를 거쳐 갈 수 있는 비용은 4 이다. 이 중 최소값은 4이다

이제 나머지 정점 중에서 가장 짧은 정점을 가지고 있는 D 를 고른다

D 노드에서 갈 수 있는 경로는 B 와 C 이다

B 의 현재 비용은 4 이고, D 를 거치는 비용은 3 이다. 이 중 최소값은 3이다

C 노드의 경우 현재 비용은 ∞ 이고, D 를 거치는 비용은 3 이다. 이 중 최소값은 3이다

이런 식으로 진행 하다보면 최소 경로를 모두 구할 수 있다

 

 

✅ 플로이드-와샬 알고리즘 (Floyd-warshall Algorithm)

# 정의

• 모든 노드 쌍들 간의 최단 경로를 구하는 방법 (All-to-All)

• 노드 집합 {1,2,3, …k} 에 속한 노드들만 거쳐 i → j 의 최단 경로를 구하는 방법은

  • k를 지나는 경우
  • k를 지나지 않는 경우

 

# 수도 코드

// k=0 일 때
for i←1 to n
	for j←1 to n
		d[i][j] = W(i,j)
		𝝿[i][j] = NIL

// 1~k 일 때
for k←1 to n
	for i←1 to n
		for j←1 to n
			d[i][j] = min(d[i][j], d[i][k]+d[k][j])
			𝝿[i][j] = k

 

• 먼저 모든 간선간의 최소비용을 세팅해준다

  • i 와 j 를 바로 잇는 간선이 존재한다면 d[i][j] = 1
  • i 와 j 를 바로 잇는 간선이 존재하지 않다면 d[i][j] = INF

• 이제 k 값을 n 까지 증가시키며 반복문을 수행한다

• k는 i → j 까지의 경로 중 거쳐야만하는 노드의 index 이다

• k를 포함한 경로와 기존 경로 중 최소값을 d[i][j] 에 저장해준다

 

# 시간 복잡도

• 플로이드 와샬 알고리즘은 3중 for문을 사용하기 때문에 O(n³) 의 시간복잡도를 가진다

• 이는 다익스트라 알고리즘이 O(n²) 의 시간복잡도를 가지고, 다익스트라의 one-to-all 을 n 번 수행한다는 점에서 같은 시간복잡도를 가지지만 플로이드 와샬은 분명한 장점을 가지고 있기 때문에 상황에 맞게 사용하면 된다!!