Algorithm/백준
[백준] DFS와 BFS(1260) - 파이썬
potato_pizza
2024. 6. 24. 14:14
728x90
DFS와 BFS(126)
https://www.acmicpc.net/problem/1260
문제
코드
- DFS, BFS의 기본 문제
- 인접 노드 리스트를 생성하고 정렬
- 방문 여부를 체크하는 초기 리스트 만들기
- DFS, BFS 각각의 결과를 저장하는 리스트틀 생성 -> 나중에 join을 활용하여 출력에 사용
- DFS, BFS 자체는 기본 공식
# DFS와 BFS
# 1260
from collections import deque
N, M, V = map(int, input().split())
graph = [[] * (N+1) for _ in range(N+1)]
# 인접노드 리스트
for i in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
graph[a].sort()
graph[b].sort()
# 방문 여부 체크
visited_dfs = [False] * (N+1)
visited_bfs = [False] * (N+1)
# 결과 창
dfs_result, bfs_result = [], []
# 1. DFS
def dfs(graph, v, visited):
visited_dfs[v] = True
# print(v, end = ' ')
dfs_result.append(v)
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph, V, visited_dfs)
# 2. BFS
def bfs(graph, start, visited):
queue = deque([start])
visited_bfs[start] = True
while queue:
v = queue.popleft()
# print(v, end = ' ')
bfs_result.append(v)
for i in graph[v]:
if not visited_bfs[i]:
queue.append(i)
visited[i] = True
bfs(graph, V, visited_bfs)
print(' '.join(map(str, dfs_result)))
print(' '.join(map(str, bfs_result)))
728x90
반응형