그래프 이론 - 8. 그래프 이론 실전 문제 풀이

 

8. 그래프 이론 실전 문제 풀이

8.1 기본적인 그래프 문제 풀이 (DFS/BFS 활용)

📌 문제 1: 미로 탈출 (BFS 활용)

[문제 설명]

• N × M 크기의 미로에서 (0,0)에서 (N-1,M-1)까지 이동하는 최단 거리를 구하는 문제
• 0은 벽, 1은 이동 가능 경로
• 가중치 없는 최단 거리 탐색 → BFS 사용

📌 제약 조건

• 2 ≤ N, M ≤ 100 (최대 10,000개의 칸)
• 0 ≤ maze[i][j] ≤ 1

📌 접근 방법 (단계별 가이드라인)

1. 입력값을 2D 리스트로 저장
2. BFS를 활용하여 (0,0)에서 (N-1,M-1)까지 이동
3. 네 방향(상,하,좌,우)으로 이동하며 방문 처리
4. 목표 지점에 도달하면 이동 횟수를 반환
5. 큐가 비었는데 도달하지 못하면 "탈출 불가능" 반환

📌 시간/공간 복잡도 분석

• 시간 복잡도: 𝑂(𝑁 × 𝑀) (모든 칸을 한 번씩 방문)
• 공간 복잡도: 𝑂(𝑁 × 𝑀) (큐와 방문 배열 저장)

📌 예제 입력

N = 5, M = 6
maze = [
    [1, 0, 1, 0, 1, 1],
    [1, 1, 1, 1, 0, 1],
    [0, 0, 0, 1, 0, 1],
    [1, 1, 1, 1, 0, 1],
    [1, 0, 0, 0, 1, 1]
]

📌 예제 출력

최단 거리: 10

📌 BFS를 활용한 미로 탈출 풀이

from collections import deque

def bfs_maze(maze):
    N, M = len(maze), len(maze[0])
    queue = deque([(0, 0, 1)])
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    visited = set()

    while queue:
        x, y, dist = queue.popleft()
        if (x, y) == (N-1, M-1):
            return f"최단 거리: {dist}"

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and maze[nx][ny] == 1 and (nx, ny) not in visited:
                queue.append((nx, ny, dist+1))
                visited.add((nx, ny))

    return "탈출 불가능"

print(bfs_maze(maze))

---

8.2 최단 경로 알고리즘 문제 풀이

📌 문제 2: 특정 노드까지의 최소 비용 경로 찾기 (다익스트라 알고리즘 활용)

[문제 설명]

• 한 도시에서 다른 도시까지 가는 최단 거리를 구하는 문제
• 모든 간선의 가중치는 양수

📌 제약 조건

• 1 ≤ N ≤ 10⁵ (최대 100,000개의 노드)
• 1 ≤ M ≤ 2 × 10⁵ (최대 200,000개의 간선)

📌 접근 방법 (단계별 가이드라인)

1. 그래프를 인접 리스트로 저장
2. 우선순위 큐를 활용하여 다익스트라 알고리즘 수행
3. 출발 노드에서 각 노드까지의 최소 비용을 갱신
4. 모든 노드의 최단 거리 값이 결정되면 결과 반환

📌 시간/공간 복잡도 분석

• 시간 복잡도: 𝑂((𝑁+𝐸) log 𝑁) (우선순위 큐 활용)
• 공간 복잡도: 𝑂(𝑁 + 𝐸) (그래프 저장 및 거리 배열)

📌 예제 입력

A →(2) B →(5) C
  ↘(1)        ↓(8)
    D  →(3)  E

📌 예제 출력

A → E 최단 거리: 4

📌 다익스트라 알고리즘 풀이

import heapq

def dijkstra(graph, start, target):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return f"{start} → {target} 최단 거리: {distances[target]}"

graph = {
    'A': [('B', 2), ('D', 1)],
    'B': [('C', 5)],
    'C': [('E', 8)],
    'D': [('E', 3)]
}

print(dijkstra(graph, 'A', 'E'))

 

---

8.3 최소 신장 트리 (MST) 문제 풀이

📌 문제 3: 도시 전력망 연결 (크루스칼 알고리즘 활용)

📌 문제 난이도: 중급
[문제 설명]

• N개의 도시를 최소 비용으로 연결하여 전력망을 구축해야 한다.
• 모든 도시는 연결되어야 하며, 최소 비용이 들어야 한다.
• 최소 신장 트리(MST) 문제로, 크루스칼 알고리즘을 사용한다.

📌 제약 조건

• 1 ≤ N ≤ 10⁵ (최대 100,000개의 도시)
• 1 ≤ M ≤ 2 × 10⁵ (최대 200,000개의 도로)

📌 접근 방법 (단계별 가이드라인)

1. 모든 도로를 가중치 기준으로 정렬
2. 유니온-파인드(Union-Find)로 사이클을 방지하며 도로 추가
3. N-1개의 도로가 선택되면 종료

📌 시간/공간 복잡도 분석

• 시간 복잡도: 𝑂(𝐸 log 𝐸) (간선 정렬 + 유니온-파인드)
• 공간 복잡도: 𝑂(𝑁) (유니온-파인드 저장)

📌 테스트 케이스

✅ 입력

도시 수: 4
도로 정보: [(0,1,4), (0,2,2), (1,2,3), (1,3,7), (2,3,5)]

✅ 출력

MST 최소 비용: 10

📌 크루스칼 알고리즘 풀이

class UnionFind:
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.rank = {i: 0 for i in range(n)}

    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            else:
                self.parent[root_u] = root_v
                if self.rank[root_u] == self.rank[root_v]:
                    self.rank[root_v] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst_cost = 0
    mst_edges = []

    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst_cost += weight
            mst_edges.append((u, v, weight))

    return f"MST 최소 비용: {mst_cost}", mst_edges

edges = [(0, 1, 4), (0, 2, 2), (1, 2, 3), (1, 3, 7), (2, 3, 5)]
print(kruskal(4, edges))

---

8.4 위상 정렬 문제 풀이

📌 문제 4: 작업 스케줄링 (위상 정렬 활용)

📌 문제 난이도: 중급
[문제 설명]

• 여러 작업 간의 의존 관계가 주어질 때, 올바른 실행 순서를 찾으라.
• 위상 정렬을 활용하여 **사이클이 없는 방향 그래프(DAG)**에서 작업 순서를 구한다.

📌 제약 조건

• 1 ≤ N ≤ 10⁵ (최대 100,000개의 작업)
• 1 ≤ M ≤ 2 × 10⁵ (최대 200,000개의 의존 관계)

📌 접근 방법 (단계별 가이드라인)

1. 진입 차수(In-degree)를 계산하여 큐에 저장
2. 진입 차수가 0인 작업을 큐에서 꺼내 수행
3. 진입 차수가 감소한 노드를 다시 큐에 추가
4. 모든 작업이 수행될 때까지 반복

📌 시간/공간 복잡도 분석

• 시간 복잡도: 𝑂(𝑁+𝐸) (모든 노드 및 간선 탐색)
• 공간 복잡도: 𝑂(𝑁) (그래프 저장)

📌 테스트 케이스

✅ 입력

작업 개수: 5
의존 관계: {'A': ['B', 'D'], 'B': ['C'], 'C': ['E'], 'D': ['E'], 'E': []}

✅ 출력

작업 실행 순서: ['A', 'B', 'D', 'C', 'E']

📌 위상 정렬 풀이

from collections import deque

def kahn_topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in in_degree if in_degree[node] == 0])
    top_order = []

    while queue:
        node = queue.popleft()
        top_order.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return f"작업 실행 순서: {top_order}"

tasks = {
    'A': ['B', 'D'],
    'B': ['C'],
    'C': ['E'],
    'D': ['E'],
    'E': []
}

print(kahn_topological_sort(tasks))