Algorithm-DFS와 BFS

---

백준 1260 : 문제링크

• 문제유형 :

  • 그래프 탐색

  • BFS DFS

• 설명

  • 정점 번호가 작은것부터 방문
  • 모든 노드와 모든 간선을 차례대로 조회하여 O(N + M)의 시간 복잡도

• 풀이

  from collections import deque
  
  def dfs(v):
      print(v, end = ' ')
      visited[v] = True
      for e in adj[v]:
          if not(visted[e])
              dfs(e)
  
  def bfs(v):
      q = deque([v])
      while q:
          v = q.popleft()
          if not(visited[v]):
              visited[v] = True
              print(v, end = ' ')
              for e in adj[v]:
                  if not visited[v]:
                      q.append(e)
  
  n, m, v = map(int, input().split())
  adj = [[] for _ in range(n + 1)]
  
  for _ in range(m):
      x, y = map(int, input().split())
      adj[x].append(y)
      adj[y].append(x)
  
  for e in adj:
      e.sort()
  
  visited = [False] * (n + 1)
  dfs(v)
  print()
  visited = [False] * (n + 1)
  bfs(v)