[Python] 1260번: DFS와 BFS

문제

코드

import sys
from collections import deque 

input = sys.stdin.readline

#깊이 우선 탐색 dfs
def dfs(graph, v, visited):
    visited[v] = True
    print(v, end= ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: # 방문하지 않았을 때
            dfs(graph, i, visited)

def bfs(graph, start, visited):
    #deque 객체 생성
    queue = deque([start])
    #노드 방문 처리
    visited[start] = True
    #queue가 빌 때까지 반복
    
    while queue:
        #queue의 최하단 요소를 제거
        v = queue.popleft()
        print(v, end=' ')
        #아직 방문하지 않은 인접한 요소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]: #아직 방문하지 않은 경우
                queue.append(i) #큐에 추가
                visited[i] = True #방문 표시



n, m, v = map(int, input().rstrip().split())

graph = [[] for _ in range(n+1)] #0번 인덱스의 노드는 비워두기

#각 노드의 방문 여부
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n+1):
    graph[i].sort()

dfs(graph, v, visited) #깊이 우선 탐색 실시

visited = [False] * (n+1) #방문 배열 초기화
print() #줄바꿈 출력
bfs(graph, v, visited) #너비 우선 탐색 실시 

DFS와 BFS 알고리즘 참고