12_graph_basic.py

  1"""
  2DFS (깊이 우선 탐색) & BFS (너비 우선 탐색)
  3Depth-First Search & Breadth-First Search
  4
  5그래프 탐색의 두 가지 기본 알고리즘입니다.
  6"""
  7
  8from collections import deque, defaultdict
  9from typing import List, Dict, Set, Optional
 10
 11
 12# =============================================================================
 13# 그래프 표현
 14# =============================================================================
 15def create_adjacency_list(edges: List[List[int]], directed: bool = False) -> Dict[int, List[int]]:
 16    """간선 리스트로부터 인접 리스트 생성"""
 17    graph = defaultdict(list)
 18    for u, v in edges:
 19        graph[u].append(v)
 20        if not directed:
 21            graph[v].append(u)
 22    return graph
 23
 24
 25# =============================================================================
 26# 1. DFS (재귀)
 27# =============================================================================
 28def dfs_recursive(graph: Dict[int, List[int]], start: int, visited: Set[int] = None) -> List[int]:
 29    """
 30    DFS 재귀 구현
 31    시간복잡도: O(V + E), 공간복잡도: O(V)
 32    """
 33    if visited is None:
 34        visited = set()
 35
 36    result = []
 37    visited.add(start)
 38    result.append(start)
 39
 40    for neighbor in graph[start]:
 41        if neighbor not in visited:
 42            result.extend(dfs_recursive(graph, neighbor, visited))
 43
 44    return result
 45
 46
 47# =============================================================================
 48# 2. DFS (스택)
 49# =============================================================================
 50def dfs_iterative(graph: Dict[int, List[int]], start: int) -> List[int]:
 51    """
 52    DFS 반복문 구현 (스택 사용)
 53    시간복잡도: O(V + E), 공간복잡도: O(V)
 54    """
 55    visited = set()
 56    stack = [start]
 57    result = []
 58
 59    while stack:
 60        node = stack.pop()
 61        if node not in visited:
 62            visited.add(node)
 63            result.append(node)
 64            # 역순으로 추가하여 작은 번호 먼저 방문
 65            for neighbor in reversed(graph[node]):
 66                if neighbor not in visited:
 67                    stack.append(neighbor)
 68
 69    return result
 70
 71
 72# =============================================================================
 73# 3. BFS
 74# =============================================================================
 75def bfs(graph: Dict[int, List[int]], start: int) -> List[int]:
 76    """
 77    BFS 구현 (큐 사용)
 78    시간복잡도: O(V + E), 공간복잡도: O(V)
 79    """
 80    visited = set([start])
 81    queue = deque([start])
 82    result = []
 83
 84    while queue:
 85        node = queue.popleft()
 86        result.append(node)
 87
 88        for neighbor in graph[node]:
 89            if neighbor not in visited:
 90                visited.add(neighbor)
 91                queue.append(neighbor)
 92
 93    return result
 94
 95
 96# =============================================================================
 97# 4. 연결 요소 찾기
 98# =============================================================================
 99def count_connected_components(n: int, edges: List[List[int]]) -> int:
100    """
101    무방향 그래프의 연결 요소 개수
102    """
103    graph = create_adjacency_list(edges, directed=False)
104    visited = set()
105    count = 0
106
107    for node in range(n):
108        if node not in visited:
109            # DFS로 연결된 모든 노드 방문
110            stack = [node]
111            while stack:
112                curr = stack.pop()
113                if curr not in visited:
114                    visited.add(curr)
115                    stack.extend(graph[curr])
116            count += 1
117
118    return count
119
120
121# =============================================================================
122# 5. 최단 거리 (BFS) - 가중치 없는 그래프
123# =============================================================================
124def shortest_path_bfs(graph: Dict[int, List[int]], start: int, end: int) -> Optional[List[int]]:
125    """
126    가중치 없는 그래프에서 최단 경로 찾기
127    """
128    if start == end:
129        return [start]
130
131    visited = set([start])
132    queue = deque([(start, [start])])
133
134    while queue:
135        node, path = queue.popleft()
136
137        for neighbor in graph[node]:
138            if neighbor == end:
139                return path + [neighbor]
140            if neighbor not in visited:
141                visited.add(neighbor)
142                queue.append((neighbor, path + [neighbor]))
143
144    return None  # 경로 없음
145
146
147# =============================================================================
148# 6. 2D 격자 탐색
149# =============================================================================
150def num_islands(grid: List[List[str]]) -> int:
151    """
152    섬의 개수 세기 (DFS)
153    '1' = 땅, '0' = 물
154    """
155    if not grid:
156        return 0
157
158    rows, cols = len(grid), len(grid[0])
159    count = 0
160
161    def dfs(r, c):
162        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
163            return
164        grid[r][c] = '0'  # 방문 표시
165        dfs(r + 1, c)
166        dfs(r - 1, c)
167        dfs(r, c + 1)
168        dfs(r, c - 1)
169
170    for r in range(rows):
171        for c in range(cols):
172            if grid[r][c] == '1':
173                count += 1
174                dfs(r, c)
175
176    return count
177
178
179# =============================================================================
180# 7. 레벨별 BFS 탐색
181# =============================================================================
182def bfs_by_level(graph: Dict[int, List[int]], start: int) -> List[List[int]]:
183    """
184    BFS 레벨(깊이)별로 노드 그룹화
185    """
186    visited = set([start])
187    queue = deque([start])
188    result = []
189
190    while queue:
191        level_size = len(queue)
192        current_level = []
193
194        for _ in range(level_size):
195            node = queue.popleft()
196            current_level.append(node)
197
198            for neighbor in graph[node]:
199                if neighbor not in visited:
200                    visited.add(neighbor)
201                    queue.append(neighbor)
202
203        result.append(current_level)
204
205    return result
206
207
208# =============================================================================
209# 8. 사이클 검출 (무방향 그래프)
210# =============================================================================
211def has_cycle_undirected(n: int, edges: List[List[int]]) -> bool:
212    """
213    무방향 그래프에서 사이클 존재 여부
214    """
215    graph = create_adjacency_list(edges, directed=False)
216    visited = set()
217
218    def dfs(node, parent):
219        visited.add(node)
220        for neighbor in graph[node]:
221            if neighbor not in visited:
222                if dfs(neighbor, node):
223                    return True
224            elif neighbor != parent:
225                return True
226        return False
227
228    for node in range(n):
229        if node not in visited:
230            if dfs(node, -1):
231                return True
232
233    return False
234
235
236# =============================================================================
237# 9. 사이클 검출 (방향 그래프)
238# =============================================================================
239def has_cycle_directed(n: int, edges: List[List[int]]) -> bool:
240    """
241    방향 그래프에서 사이클 존재 여부
242    상태: 0=미방문, 1=방문중(현재 경로), 2=완료
243    """
244    graph = create_adjacency_list(edges, directed=True)
245    state = [0] * n  # 0: 미방문, 1: 방문중, 2: 완료
246
247    def dfs(node):
248        if state[node] == 1:  # 방문 중인 노드 재방문 = 사이클
249            return True
250        if state[node] == 2:  # 이미 완료된 노드
251            return False
252
253        state[node] = 1  # 방문 시작
254
255        for neighbor in graph[node]:
256            if dfs(neighbor):
257                return True
258
259        state[node] = 2  # 방문 완료
260        return False
261
262    for node in range(n):
263        if state[node] == 0:
264            if dfs(node):
265                return True
266
267    return False
268
269
270# =============================================================================
271# 테스트
272# =============================================================================
273def main():
274    print("=" * 60)
275    print("DFS & BFS 예제")
276    print("=" * 60)
277
278    # 그래프 생성
279    edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]
280    graph = create_adjacency_list(edges)
281
282    print("\n[그래프 구조]")
283    print("       0")
284    print("      / \\")
285    print("     1   2")
286    print("    /|   |\\")
287    print("   3 4   5 6")
288
289    # 1. DFS (재귀)
290    print("\n[1] DFS (재귀)")
291    result = dfs_recursive(graph, 0)
292    print(f"    시작: 0, 탐색 순서: {result}")
293
294    # 2. DFS (반복)
295    print("\n[2] DFS (반복/스택)")
296    result = dfs_iterative(graph, 0)
297    print(f"    시작: 0, 탐색 순서: {result}")
298
299    # 3. BFS
300    print("\n[3] BFS")
301    result = bfs(graph, 0)
302    print(f"    시작: 0, 탐색 순서: {result}")
303
304    # 4. 연결 요소
305    print("\n[4] 연결 요소 개수")
306    edges2 = [[0, 1], [1, 2], [3, 4]]
307    count = count_connected_components(5, edges2)
308    print(f"    노드 5개, 간선: {edges2}")
309    print(f"    연결 요소 개수: {count}")
310
311    # 5. 최단 경로
312    print("\n[5] 최단 경로 (BFS)")
313    path = shortest_path_bfs(graph, 0, 6)
314    print(f"    0 -> 6 최단 경로: {path}")
315
316    # 6. 섬 개수 세기
317    print("\n[6] 섬의 개수")
318    grid = [
319        ['1', '1', '0', '0', '0'],
320        ['1', '1', '0', '0', '0'],
321        ['0', '0', '1', '0', '0'],
322        ['0', '0', '0', '1', '1']
323    ]
324    # 복사본 사용 (원본 변경됨)
325    grid_copy = [row[:] for row in grid]
326    count = num_islands(grid_copy)
327    print(f"    격자:")
328    for row in grid:
329        print(f"    {row}")
330    print(f"    섬의 개수: {count}")
331
332    # 7. 레벨별 BFS
333    print("\n[7] 레벨별 BFS 탐색")
334    levels = bfs_by_level(graph, 0)
335    for i, level in enumerate(levels):
336        print(f"    레벨 {i}: {level}")
337
338    # 8. 사이클 검출 (무방향)
339    print("\n[8] 사이클 검출 (무방향 그래프)")
340    edges_no_cycle = [[0, 1], [1, 2], [2, 3]]
341    edges_with_cycle = [[0, 1], [1, 2], [2, 0]]
342    print(f"    간선 {edges_no_cycle}: 사이클 = {has_cycle_undirected(4, edges_no_cycle)}")
343    print(f"    간선 {edges_with_cycle}: 사이클 = {has_cycle_undirected(3, edges_with_cycle)}")
344
345    # 9. 사이클 검출 (방향)
346    print("\n[9] 사이클 검출 (방향 그래프)")
347    edges_dag = [[0, 1], [1, 2], [0, 2]]
348    edges_cycle = [[0, 1], [1, 2], [2, 0]]
349    print(f"    DAG {edges_dag}: 사이클 = {has_cycle_directed(3, edges_dag)}")
350    print(f"    간선 {edges_cycle}: 사이클 = {has_cycle_directed(3, edges_cycle)}")
351
352    print("\n" + "=" * 60)
353
354
355if __name__ == "__main__":
356    main()