반응형
그래프 알고리즘
그래프 알고리즘은 노드(정점)와 노드를 연결하는 에지(간선)로 구성된 자료구조인 그래프를 탐색하거나 분석하는 알고리즘입니다. 이번 글에서는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 그리고 최단 경로 알고리즘(Dijkstra, Floyd-Warshall)에 대해 알아보겠습니다.
깊이 우선 탐색(DFS)
깊이 우선 탐색(DFS)은 그래프의 모든 정점을 깊게 탐색하는 알고리즘입니다. 스택(또는 재귀)을 사용하여 구현할 수 있습니다.
예제: DFS 구현
JavaScript
class Graph {
constructor() {
this.adjList = new Map();
}
addVertex(v) {
if (!this.adjList.has(v)) {
this.adjList.set(v, []);
}
}
addEdge(v, w) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
}
dfs(startingNode) {
let visited = new Set();
this._dfsUtil(startingNode, visited);
}
_dfsUtil(v, visited) {
visited.add(v);
console.log(v);
let neighbors = this.adjList.get(v);
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
this._dfsUtil(neighbor, visited);
}
}
}
}
let g = new Graph();
let vertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for (let i = 0; i < vertices.length; i++) {
g.addVertex(vertices[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
console.log("DFS:");
g.dfs('A');Python
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, v):
if v not in self.adj_list:
self.adj_list[v] = []
def add_edge(self, v, w):
if v in self.adj_list and w in self.adj_list:
self.adj_list[v].append(w)
self.adj_list[w].append(v)
def dfs(self, starting_node):
visited = set()
self._dfs_util(starting_node, visited)
def _dfs_util(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbor in self.adj_list[v]:
if neighbor not in visited:
self._dfs_util(neighbor, visited)
g = Graph()
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
for vertex in vertices:
g.add_vertex(vertex)
g.add_edge('A', 'B')
g.add_edge('A', 'D')
g.add_edge('A', 'E')
g.add_edge('B', 'C')
g.add_edge('D', 'E')
g.add_edge('E', 'F')
g.add_edge('E', 'C')
g.add_edge('C', 'F')
print("DFS:")
g.dfs('A') # A B C E F D너비 우선 탐색(BFS)
너비 우선 탐색(BFS)은 그래프의 모든 정점을 너비 우선으로 탐색하는 알고리즘입니다. 큐를 사용하여 구현할 수 있습니다.
예제: BFS 구현
JavaScript
class Graph {
constructor() {
this.adjList = new Map();
}
addVertex(v) {
if (!this.adjList.has(v)) {
this.adjList.set(v, []);
}
}
addEdge(v, w) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
}
bfs(startingNode) {
let visited = new Set();
let queue = [startingNode];
visited.add(startingNode);
while (queue.length > 0) {
let v = queue.shift();
console.log(v);
let neighbors = this.adjList.get(v);
for (let neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
}
let g = new Graph();
let vertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for (let i = 0; i < vertices.length; i++) {
g.addVertex(vertices[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
console.log("BFS:");
g.bfs('A');Python
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, v):
if v not in self.adj_list:
self.adj_list[v] = []
def add_edge(self, v, w):
if v in self.adj_list and w in self.adj_list:
self.adj_list[v].append(w)
self.adj_list[w].append(v)
def bfs(self, starting_node):
visited = set()
queue = [starting_node]
visited.add(starting_node)
while queue:
v = queue.pop(0)
print(v, end=' ')
for neighbor in self.adj_list[v]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
g = Graph()
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
for vertex in vertices:
g.add_vertex(vertex)
g.add_edge('A', 'B')
g.add_edge('A', 'D')
g.add_edge('A', 'E')
g.add_edge('B', 'C')
g.add_edge('D', 'E')
g.add_edge('E', 'F')
g.add_edge('E', 'C')
g.add_edge('C', 'F')
print("BFS:")
g.bfs('A') # A B D E C F최단 경로 알고리즘
Dijkstra 알고리즘
Dijkstra 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 그래프에서 사용되며, 우선순위 큐를 이용해 구현할 수 있습니다.
예제: Dijkstra 알고리즘 구현
JavaScript
class PriorityQueue {
constructor() {
this.items = [];
}
enqueue(element, priority) {
let queueElement = { element, priority };
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
this.items.push(queueElement);
}
}
dequeue() {
return this.items.shift();
}
isEmpty() {
return this.items.length === 0;
}
}
class Graph {
constructor() {
this.adjList = new Map();
}
addVertex(v) {
if (!this.adjList.has(v)) {
this.adjList.set(v, []);
}
}
addEdge(v, w, weight) {
this.adjList.get(v).push({ node: w, weight });
this.adjList.get(w).push({ node: v, weight });
}
dijkstra(start) {
let distances = {};
let pq = new PriorityQueue();
let prev = {};
this.adjList.forEach((_, vertex) => {
distances[vertex] = Infinity;
prev[vertex] = null;
});
distances[start] = 0;
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
let { element: current } = pq.dequeue();
this.adjList.get(current).forEach(neighbor => {
let distance = distances[current] + neighbor.weight;
if (distance < distances[neighbor.node]) {
distances[neighbor.node] = distance;
prev[neighbor.node] = current;
pq.enqueue(neighbor.node, distance);
}
});
}
return distances;
}
}
let g = new Graph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addVertex('E');
g.addVertex('F');
g.addEdge('A', 'B', 4);
g.addEdge('A', 'C', 2);
g.addEdge('B', 'E', 3);
g.addEdge('C', 'D', 2);
g.addEdge('C', 'F', 4);
g.addEdge('D', 'E', 3);
g.addEdge('D', 'F', 1);
g.addEdge('E', 'F', 1);
console.log(g.dijkstra('A'));Python
import heapq
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, v):
if v not in self.adj_list:
self.adj_list[v] = []
def add_edge(self, v, w, weight):
self.adj_list[v].append((w, weight))
self.adj_list[w].append((v, weight))
def dijkstra(self, start):
distances = {vertex: float('infinity') for vertex in self.adj_list}
distances[start] = 0
pq = [(0, start)]
prev = {vertex: None for vertex in self.adj_list}
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in self.adj_list[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
prev[neighbor] = current_vertex
heapq.heappush(pq, (distance, neighbor))
return distances
g = Graph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_vertex('D')
g.add_vertex('E')
g.add_vertex('F')
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'E', 3)
g.add_edge('C', 'D', 2)
g.add_edge('C', 'F', 4)
g.add_edge('D', 'E', 3)
g.add_edge('D', 'F', 1)
g.add_edge('E', 'F', 1)
print(g.dijkstra('A'))Floyd-Warshall 알고리즘
Floyd-Warshall 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다. 시간 복잡도는 O(n^3)입니다.
예제: Floyd-Warshall 알고리즘 구현
JavaScript
function floydWarshall(graph) {
let dist = [];
let size = graph.length;
for (let i = 0; i < size; i++) {
dist[i] = [];
for (let j = 0; j < size; j++) {
if (i === j) {
dist[i][j] = 0;
} else if (graph[i][j] !== 0) {
dist[i][j] = graph[i][j];
} else {
dist[i][j] = Infinity;
}
}
}
for (let k = 0; k < size; k++) {
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
let graph = [
[0, 3, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 7, 0, 2],
[0, 0, 0, 0, 0, 3],
[0, 0, 0, 2, 0, 0],
[0, 0, 0, 0, 1, 0]
];
console.log(floydWarshall(graph));Python
def floyd_warshall(graph):
size = len(graph)
dist = [[float('inf')] * size for _ in range(size)]
for i in range(size):
for j in range(size):
if i == j:
dist[i][j] = 0
elif graph[i][j] != 0:
dist[i][j] = graph[i][j]
for k in range(size):
for i in range(size):
for j in range(size):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
graph = [
[0, 3, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 7, 0, 2],
[0, 0, 0, 0, 0, 3],
[0, 0, 0, 2, 0, 0],
[0, 0, 0, 0, 1, 0]
]
print(floyd_warshall(graph))연습 문제
문제 1: 두 정점 간의 최단 경로 찾기
주어진 그래프에서 두 정점 간의 최단 경로를 찾는 프로그램을 작성하세요.
JavaScript
class Graph {
constructor() {
this.adjList = new Map();
}
addVertex(v) {
if (!this.adjList.has(v)) {
this.adjList.set(v, []);
}
}
addEdge(v, w, weight) {
this.adjList.get(v).push({ node: w, weight });
this.adjList.get(w).push({ node: v, weight });
}
dijkstra(start, end) {
let distances = {};
let pq = new PriorityQueue();
let prev = {};
this.adjList.forEach((_, vertex) => {
distances[vertex] = Infinity;
prev[vertex] = null;
});
distances[start] = 0;
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
let { element: current } = pq.dequeue();
if (current === end) {
let path = [];
while (prev[current]) {
path.push(current);
current = prev[current];
}
path.push(start);
return path.reverse();
}
this.adjList.get(current).forEach(neighbor => {
let distance = distances[current] + neighbor.weight;
if (distance < distances[neighbor.node]) {
distances[neighbor.node] = distance;
prev[neighbor.node] = current;
pq.enqueue(neighbor.node, distance);
}
});
}
return [];
}
}
let g = new Graph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addVertex('E');
g.addVertex('F');
g.addEdge('A', 'B', 4);
g.addEdge('A', 'C', 2);
g.addEdge('B', 'E', 3);
g.addEdge('C', 'D', 2);
g.addEdge('C', 'F', 4);
g.addEdge('D', 'E', 3);
g.addEdge('D', 'F', 1);
g.addEdge('E', 'F', 1);
console.log(g.dijkstra('A', 'E'));Python
import heapq
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, v):
if v not in self.adj_list:
self.adj_list[v] = []
def add_edge(self, v, w, weight):
self.adj_list[v].append((w, weight))
self.adj_list[w].append((v, weight))
def dijkstra(self, start, end):
distances = {vertex: float('infinity') for vertex in self.adj_list}
distances[start] = 0
pq = [(0, start)]
prev = {vertex: None for vertex in self.adj_list}
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_vertex == end:
path = []
while prev[current_vertex]:
path.append(current_vertex)
current_vertex = prev[current_vertex]
path.append(start)
return path[::-1]
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in self.adj_list[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
prev[neighbor] = current_vertex
heapq.heappush(pq, (distance, neighbor))
return []
g = Graph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_vertex('D')
g.add_vertex('E')
g.add_vertex('F')
g.add_edge('A', 'B',
4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'E', 3)
g.add_edge('C', 'D', 2)
g.add_edge('C', 'F', 4)
g.add_edge('D', 'E', 3)
g.add_edge('D', 'F', 1)
g.add_edge('E', 'F', 1)
print(g.dijkstra('A', 'E'))결론
이번 글에서는 코딩 테스트 준비를 위해 그래프 알고리즘에 대해 배웠습니다. 이를 통해 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 최단 경로 알고리즘(Dijkstra, Floyd-Warshall)의 개념과 구현 방법을 익힐 수 있었습니다. 다음 글에서는 동적 프로그래밍에 대해 알아보겠습니다.
다음 글에서 만나요!
반응형
'코딩테스트1' 카테고리의 다른 글
| [코딩 테스트] 14일차: 분할 정복 (1) | 2024.09.14 |
|---|---|
| [코딩 테스트] 13일차: 동적 프로그래밍 (0) | 2024.09.13 |
| [코딩 테스트] 11일차: 재귀와 백트래킹 (0) | 2024.09.11 |
| [코딩 테스트] 10일차: 탐색 알고리즘 (0) | 2024.09.10 |
| [코딩 테스트] 9일차: 정렬 알고리즘 (0) | 2024.09.09 |