백준 1260번 - DFS와 BFS (Python3)

코드

from collections import deque
# 슈퍼 기본 DFS & BFS
n, m, v = map(int, input().split())

# 리스트의 첫번째 요소는 빈 리스트 처리 => 인덱스 번호와 노드 번호를 통일시키기 위해서
# 따라서 n + 1 => 정점 개수 +1 만큼 반복해야함
graph = [[] for _ in range(n + 1)]

# 각 노드마다 방문 여부 체크할 리스트 선언
visited = [False] * (n + 1)

# 입력받은 노드와 간선간의 연결 정보를 노드별 인접리스로 표현
for _ in range(m):
    
    # 간선이 연결하는 두 정점의 번호 입력
    a, b = map(int, input().split())
    
    # a와 b 노드가 연결돼어있다 = b와 a 노드가 연결돼어있다 (swap)
    graph[a].append(b)
    graph[b].append(a)
    
    # 번확 작은 순서로 방문하기 때문에 sort()로 오름차순 정렬 시행
    graph[a].sort()
    graph[b].sort()

# DFS 
def dfs(graph, v, visited):
    # 시작 방문 처리 & 재귀적 호출 시 새로 받은 v번째 노드 방문처리
    visited[v] = True
            
    # 방문한 노드의 번호 출력
    print(v, end = ' ')
    
    # 처음 시작 노드의 번호 v부터 v에 연결되어있는 노드들을 반복하여 탐색 시작
    for i in graph[v]:
        
        # v번 노드의 방문 여부가 False이면
        if not visited[i]:
            
            # 재귀적으로 호출 => 스택 구현과 동일한 기능
            dfs(graph, i, visited)
# BFS      
def bfs(graph, v, visited):
    # 방문 여부 리스트 초기화
    visited = [False] * (n + 1)
    
    # 방문 노드를 담을 queue 선언
    queue = deque()
    
    # 시작 노드 방문
    queue.append(v)
    
    # 시작 방문 처리 & 재귀적 호출 시 새로 받은 v번째 노드 방문처리
    visited[v] = True
    
    # 방문을 완료한 원소들을 queue에 넣고 queue에서 하나씩 순서대로 뽑아내면
    # queue가 빌 것이고 그럴 경우 반복문 종료
    while queue:
        # 큐에서 LILO로 원소 출력
        p = queue.popleft()
        print(p, end=' ')
        
        # 해당 요소와 연결된 미방문 노드들 큐에 삽입 후 방문처리
        for i in graph[p]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
dfs(graph, v, visited)
print()
bfs(graph, v, visited)