[백준 1260번] DFS와 BFS

BFS => 주위에서 읽는거, 옆으로 퍼지는 알고리즘

DFS => 한번 깊이 빠져드는거, 재귀적

그래프를 DFS와 BFS 로 출력하는 프로그램.

입력은 N(1,000까지) 엣지는 (10,000까지) 탐색을 시작할번호 V

첫줄 (예시 1 : 4 5 1 -> 4개 노드, 5개 엣지, 시작 1)

출력은

첫쨋줄 : DFS 방식 - 이동 순서 (예시 1 : 1 2 4 3) : 이진트리

다음줄에는 BFS - 이동 순서

2초 안에 계산

시간복잡도 : (V+E)

# 알고리즘 DFS, BFS
# 시간복잡도 (V+E)

import sys
from collections import deque

def DFS(cur, graph, visited):
    visited[cur] = True
    print(cur, end=' ')
    
    for idx in graph[cur]:
        if not visited[idx]:
            DFS(idx, graph, visited)

def BFS(cur, graph, visited):
    visited[cur] = True
    queue = deque([cur])
    
    while queue:
        cur_node = queue.popleft()
        print(cur_node, end=' ')
        
        for idx in graph[cur_node]:
            if not visited[idx]:
                visited[idx] = True
                queue.append(idx)

def main():
    N,M,V = map(int, sys.stdin.readline().split())
    
    graph = [ [] for _ in range(N+1)]
    
    for i in range(M):
        u,v = map(int, sys.stdin.readline().split())
        graph[u].append(v)
        graph[v].append(u)
        
    # 작은것부터 정렬
    for i in range(1,N+1):
        graph[i].sort()
        
    # DFS 실행
    visited_dfs = [False]*(N+1)
    DFS(V, graph, visited_dfs)
    print()
        
    # BFS 실행
    visited_bfs = [False]*(N+1)
    BFS(V, graph, visited_bfs)
    
if __name__ == "__main__":
    main()