import sys
from collections import deque
N, M, V = map(int,sys.stdin.readline().split())
#graph 입력 받기
graph = [[0]* (N+1) for i in range(N+1)]
for i in range(M):
a, b = map(int, sys.stdin.readline().split())
graph[a][b] = graph[b][a] = 1
dfs_visited = [0] * (N+1)
def dfs(start_Node):
dfs_visited[start_Node] = 1
print(start_Node, end = ' ')
for i in range(1, N+1):
if dfs_visited[i] == 0 and graph[start_Node][i] == 1:
dfs(i)
bfs_visited = [0] * (N+1)
def bfs(start_Node):
queue = deque()
queue.append(start_Node)
bfs_visited[start_Node] = 1
while queue:
start_Node = queue.popleft()
print(start_Node, end= ' ')
for i in range(1, N+1):
if bfs_visited[i] == 0 and graph[start_Node][i] == 1:
queue.append(i)
bfs_visited[i] = 1
dfs(V)
print()
bfs(V)
graph를 받을 때 undirected graph라서 양쪽으로 모두 연결시켜주어야 한다.
DFS
먼저 파라미터로 받은 start_Node를 방문처리하고, 출력한다. 그리고 graph에서 start_Node와 연결되어 있고 방문하지 않은 노드로 다시 dfs를 수행한다.
BFS
deque로 큐를 만들고, start_Node를 큐에 넣는다. 그리고 출력한다. start_Node와 연결되어 있고 방문하지 않은 노드는 큐에 넣고, 방문처리한다.
728x90
'파이썬 알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 1697번 숨바꼭질 BFS (2) | 2024.02.20 |
---|---|
[백준] 117번 DFS와 BFS 다시 풀기 (0) | 2024.02.20 |
[프로그래머스] Lv1. 이상한 문자 만들기 파이썬 (1) | 2024.02.11 |
[프로그래머스] Lv.3 단어변환 dfs bfs 파이썬 (2) | 2024.02.11 |
[프로그래머스] Lv1. 체육복 파이썬 (1) | 2024.02.11 |