[백준|파이썬] 1260: DFS와 BFS (실버2)

문제

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

1260번: DFS와 BFS

 

 

🐍파이썬

import sys

N, M, V = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]

for i in range(M):
    a, b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in graph:	#숫자가 낮은 노드부터 탐색시키기 위해 정렬
      i.sort()

def DFS(v):
    visited[v] = True	#노드v 방문처리
    print(v, end=' ')	#방문한 노드 출력
    for i in graph[v]:	#노드v와 연결된 모든 노드에 대해
        if not visited[i]:	#노드i에 방문한 적이 없다면
            DFS(i)	#노드i를 기준으로 깊이탐색

def BFS(start):
    queue.append(start)	#큐에 시작노드 삽입
    visited[start] = True	#시작노드 방문처리
    while queue:	#큐가 빌때까지 반복
        v = queue.pop(0)	#큐의 가장 왼쪽에서 원소 하나를 꺼냄
        print(v, end=' ')	#꺼낸 원소를 출력
        for i in graph[v]:	#꺼낸 원소와 연결된 모든 노드에 대해
            if not visited[i]:	#i에 방문한 적이 없다면
                queue.append(i)	#i를 큐에 넣기
                visited[i] = True	#i를 방문처리

visited = [False] * (N+1)
DFS(V)

print()

queue = []
visited = [False] * (N+1)
BFS(V)

 

 

참고한 블로그

풀이 참고

https://ji-gwang.tistory.com/291

백준 1260번 파이썬 문제풀이(큐와 그래프 - DFS와 BFS)

 

이론 참고

https://vanillacreamdonut.tistory.com/214

[Python] DFS / BFS 정리