백준 24479번 깊이 우선탐색-1

깊이 우선탐색 문제로 깊이 우선 탐색이란 노드에서 좌우로 움직이는 것(bfs)이 아닌 세로로 움직이는것이다 한방향을 계속 가다가 더이상 가지 못하면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다시 탐색을 진행하는 방법이다

• 넓게보다는 깊이를 우선적으로 탐색

• 모든 노드를 방문하고자 하는 경우 사용한다

• 너비 우선 탐색(bfs)보다 간편하다

• 너비 우선 탐색보다 느리다

   

  자신을 호출하는 순환 알고리즘 형태를 가지고 있어서 어떤 노드를 방문했는지 기록하지 않으면 무한 루프에 빠질 수 있다

  ---

   

   

  이번 문제는 dfs알고리즘을 이용해서 노드를 모두 방문하고 각노드 1번 노드부터 방문순서를 출력하는 문제다 노드의 간선정보를 이중리스트를 사용하여 저장한후에 오름차순 으로 방문하기 때문에 오름차순으로 정렬한다 그뒤 dfs알고리즘으로 노드를 방문하고 만약 방문했으면 다음 노드를 확인하지만 방문이 없으면 현재 방문순서를 기입하고 방문순서를 +1한다 끝까지 돌리고 각 노드의 방문 순서를 출력한다

  def dfs(k): #방문 순서를 ans리스트에 기록한다
      global cur
      ans[k] = cur
      for to_go in link[k]:
          if ans[to_go]:
              continue
          cur+=1
          dfs(to_go) 
    
  import sys
  input = sys.stdin.readline
  sys.setrecursionlimit(1000000) #RecursionError해결
    
  n,m,r = map(int,input().split())
  cur = 1 #시작정점을 위한것
  link = [[] for _ in range(n+1)]
  ans=[0]*(n+1) #노드의 방문순서를 기록하기 위한 리스트
    
  for _ in range(1,m+1):
      a,b = map(int,input().split())
      link[a].append(b)
      link[b].append(a)
    
  for lis in link:
      lis.sort()#오름차순으로 정렬
    
  dfs(r)
    
  for i in ans[1:]:
      print(i)