DFS, BFS

나중에 완성하기

---

https://www.acmicpc.net/problem/1260

1from collections import defaultdict, deque
2from typing import Any
3import sys
4
5# 입력 받기
6n, m, v = map(int, sys.stdin.readline().split())
7
8# 그래프 정의
9graph = defaultdict(list)
10for _ in range(m):
11    a, b = map(int, sys.stdin.readline().split())
12    graph[a].append(b)
13    graph[b].append(a)
14
15# 각 노드의 연결 리스트 정렬
16for key in graph:
17    graph[key].sort()
18
19# DFS 함수
20def dfs(graph: defaultdict[Any, list], start: int):
21    visited = []
22    stack = [start]
23    visited_set = set()
24
25    while stack:
26        node = stack.pop()
27        if node not in visited_set:
28            visited.append(node)
29            visited_set.add(node)
30            # 다음에 방문할 노드 추가 (오름차순 방문을 위해 역순으로 추가)
31            stack.extend(reversed(graph[node]))
32
33    return visited
34
35# BFS 함수
36def bfs(graph: defaultdict[Any, list], start: int):
37    visited = []
38    queue = deque([start])
39    visited_set = set([start])
40
41    while queue:
42        node = queue.popleft()
43        visited.append(node)
44
45        for neighbor in graph[node]:
46            if neighbor not in visited_set:
47                visited_set.add(neighbor)
48                queue.append(neighbor)
49
50    return visited
51
52# 출력
53print(" ".join(map(str, dfs(graph, v))))
54print(" ".join(map(str, bfs(graph, v))))

---

💡 마무리

나중에 완성하기