1260. DFS와 BFS

업데이트 시간 : 2023-02-06 07:15:19 +0000

[Silver II] DFS와 BFS - 1260

성능 요약

메모리: 34176 KB, 시간: 484 ms

분류

그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

💡 Solutions

📄 DFS와 BFS.py

from collections import deque

# T = int(input())

N,M,V = map(int,input().split())

net = dict()
for _ in range(M):
  s, e = map(int,input().split())
  if not net.get(s) or not net.get(e):
    net.setdefault(s, set())
    net.setdefault(e, set())
  net[s].add(e)
  net[e].add(s)
  
is_travel_dfs = [False for _ in range(N+1)]
is_travel_bfs = [False for _ in range(N+1)]


def dfs(n):

  print(n,end =' ')
  
  if net.get(n):
    connect = sorted(list(net[n]))
    for item in connect:
      if is_travel_dfs[item]: continue
      is_travel_dfs[item] = True
      dfs(item)

queue = deque()
def bfs(n):
  
  is_travel_bfs[n] = True
  
  
  queue.append(n)
  
  while queue:
    now = queue.popleft()
    print(now,end =' ')
    if net.get(now):
      now_lst = sorted(list(net[now]))
      for item in now_lst:
        if is_travel_bfs[item]:
          continue
        is_travel_bfs[item] = True
        queue.append(item)
        
  
  # if net.get(n):
  #   connect = sorted(list(net[n]))
  #   for item in connect:
  #     if is_travel_bfs[item]: continue
  #     is_travel_bfs[item] = True
  #     queue.append(item)
    
  #   try:
  #     bfs(queue.pop(0))
  #   except:
  #     return 

is_travel_dfs[V] = True
dfs(V)
print()
bfs(V)