Python/DFS&BFS
99클럽 코테 스터디 6일차 TIL + 백준 1260 DFS와 BFS (파이썬)
유일리
2025. 1. 21. 12:23
※ 1260 DFS와 BFS
https://www.acmicpc.net/problem/1260
문제 해결 TIP
DFS는 스택으로, BFS는 큐로 구현한다.
문제 해결 풀이
그래프 리스트에 각 노드가 연결된 정보를 표현한다.
전체 코드
from collections import deque
N, M, V = map(int,input().split())
graph=[[] for _ in range(N+1)]
for i in range(M):
num1,num2 = map(int,input().split())
graph[num1].append(num2)
graph[num2].append(num1)
graph = [sorted(g) for g in graph]
visited = [False]*(N+1)
graph2 = graph.copy()
visited2 = visited.copy()
def bfs(graph,start,visited):
queue = deque([start])
visited[start] = True
while queue:
v= queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph2,V,visited2)
print()
bfs(graph,V,visited)
- 비기너 문제 : 할리갈리 https://www.acmicpc.net/problem/27160
- 미들러 문제 : DFS와 BFS https://www.acmicpc.net/problem/1260
- 챌린저 문제 : 특정한 최단 경로 https://www.acmicpc.net/problem/1504