[코딩테스트] 3주차: 그래프 알고리즘

그래프 알고리즘

학습 주제:

• 그래프의 표현 방법 (인접 행렬, 인접 리스트)
• 그래프 탐색 알고리즘 (DFS, BFS)
• 최단 경로 알고리즘 (Dijkstra, Floyd-Warshall)

학습 목표:

• 그래프의 표현 방법을 이해하고 구현할 수 있다.
• 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘을 이해하고 적용할 수 있다.
• 다양한 최단 경로 알고리즘을 이해하고 문제에 적용할 수 있다.

학습 자료:

• 그래프의 표현 방법 설명 및 구현
• 깊이 우선 탐색(DFS) 알고리즘 설명 및 구현
• 너비 우선 탐색(BFS) 알고리즘 설명 및 구현
• Dijkstra 알고리즘 설명 및 구현
• Floyd-Warshall 알고리즘 설명 및 구현

실습 문제:

1. 그래프 표현 방법

• 인접 행렬과 인접 리스트를 사용하여 그래프를 구현하세요.

# 인접 행렬
def create_adj_matrix(vertices):
    adj_matrix = [[0 for _ in range(vertices)] for _ in range(vertices)]
    return adj_matrix

def add_edge_adj_matrix(matrix, u, v):
    matrix[u][v] = 1
    matrix[v][u] = 1

# 인접 리스트
from collections import defaultdict

def create_adj_list():
    adj_list = defaultdict(list)
    return adj_list

def add_edge_adj_list(adj_list, u, v):
    adj_list[u].append(v)
    adj_list[v].append(u)

# Test
vertices = 5
adj_matrix = create_adj_matrix(vertices)
add_edge_adj_matrix(adj_matrix, 0, 1)
add_edge_adj_matrix(adj_matrix, 0, 4)
add_edge_adj_matrix(adj_matrix, 1, 2)
add_edge_adj_matrix(adj_matrix, 1, 3)
add_edge_adj_matrix(adj_matrix, 1, 4)
add_edge_adj_matrix(adj_matrix, 2, 3)
add_edge_adj_matrix(adj_matrix, 3, 4)
print("Adjacency Matrix:")
for row in adj_matrix:
    print(row)

adj_list = create_adj_list()
add_edge_adj_list(adj_list, 0, 1)
add_edge_adj_list(adj_list, 0, 4)
add_edge_adj_list(adj_list, 1, 2)
add_edge_adj_list(adj_list, 1, 3)
add_edge_adj_list(adj_list, 1, 4)
add_edge_adj_list(adj_list, 2, 3)
add_edge_adj_list(adj_list, 3, 4)
print("Adjacency List:")
for key in adj_list:
    print(f"{key}: {adj_list[key]}")

 

2. 깊이 우선 탐색 (DFS)

• 주어진 그래프에 대해 깊이 우선 탐색을 수행하는 함수를 작성하세요.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next in graph[start]:
        if next not in visited:
            dfs(graph, next, visited)

# Test
graph = {0: [1, 4], 1: [0, 2, 3, 4], 2: [1, 3], 3: [1, 2, 4], 4: [0, 1, 3]}
print("DFS:")
dfs(graph, 0)

 

3. 너비 우선 탐색 (BFS)

• 주어진 그래프에 대해 너비 우선 탐색을 수행하는 함수를 작성하세요.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Test
print("\nBFS:")
bfs(graph, 0)

 

4. Dijkstra 알고리즘

• 주어진 그래프에 대해 Dijkstra 알고리즘을 사용하여 최단 경로를 찾는 함수를 작성하세요.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

# Test
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("\nDijkstra:")
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

5. Floyd-Warshall 알고리즘

• 주어진 그래프에 대해 Floyd-Warshall 알고리즘을 사용하여 모든 쌍 최단 경로를 찾는 함수를 작성하세요.

def floyd_warshall(graph):
    distance = list(map(lambda i: list(map(lambda j: j, i)), graph))
    V = len(graph)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    return distance

# Test
INF = float('infinity')
graph = [
    [0, 3, INF, 5],
    [2, 0, INF, 4],
    [INF, 1, 0, INF],
    [INF, INF, 2, 0]
]
print("\nFloyd-Warshall:")
dist = floyd_warshall(graph)
for row in dist:
    print(row)

 

추가 학습 자료:

• Graph Data Structures - GeeksforGeeks
• DFS and BFS - GeeksforGeeks
• Dijkstra's Algorithm - GeeksforGeeks
• Floyd-Warshall Algorithm - GeeksforGeeks

---

백준 (Baekjoon) 문제

1. 문제명: DFS와 BFS
   • 설명: 주어진 그래프에 대해 DFS와 BFS를 수행하는 문제입니다.
   • 문제 유형: 그래프 탐색 (DFS, BFS)
   • 난이도: 실버 II
   • 주소: DFS와 BFS
2. 문제명: 최소비용 구하기
   • 설명: 주어진 그래프에서 두 노드 사이의 최단 경로를 찾는 문제입니다. Dijkstra 알고리즘을 활용합니다.
   • 문제 유형: 최단 경로 (Dijkstra)
   • 난이도: 골드 V
   • 주소: 최소비용 구하기
3. 문제명: 플로이드
   • 설명: 주어진 그래프에서 모든 쌍의 최단 경로를 찾는 문제입니다. Floyd-Warshall 알고리즘을 활용합니다.
   • 문제 유형: 최단 경로 (Floyd-Warshall)
   • 난이도: 골드 IV
   • 주소: 플로이드

프로그래머스 (Programmers) 문제

1. 문제명: 가장 먼 노드
   • 설명: 주어진 그래프에서 특정 노드로부터 가장 먼 노드를 찾는 문제입니다.
   • 문제 유형: 그래프 탐색 (BFS)
   • 난이도: 레벨 3
   • 주소: 가장 먼 노드
2. 문제명: 순위
   • 설명: 주어진 그래프에서 순위를 매기는 문제입니다. Floyd-Warshall 알고리즘을 활용합니다.
   • 문제 유형: 그래프 탐색 (Floyd-Warshall)
   • 난이도: 레벨 3
   • 주소: 순위
3. 문제명: 가장 빠른 길 찾기
   • 설명: 주어진 그래프에서 두 노드 사이의 최단 경로를 찾는 문제입니다. Dijkstra 알고리즘을 활용합니다.
   • 문제 유형: 최단 경로 (Dijkstra)
   • 난이도: 레벨 3
   • 주소: 가장 빠른 길 찾기