[22.08.10] DFS

깊이 우선 탐색 (DFS)

#dfs #bfs #그래프

1. 그래프 탐색 알고리즘

   데이터 구조는 알고리즘의 재료가 되어 문제 해결에 사용 된다.

   그래프 자료구조는 탐색 알고리즘에 활용된다.

   • 그래프 탐색 알고리즘이란?

     시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 찾는 알고리즘

   • 깊이 우선 탐색 DFS (Depth First Search) [ 그래프 + 스택 ]

     그래프의 깊이르 우선으로 탐색하기 위해 스택의 개념을 활용

   • 너비 우선 탐색 BFS (Breadth First Search) [ 그래프 + 큐 ]

     그래프의 너비를 우선으로 탐색하기 위해 큐의 개념을 활용

2. 깊이우선탐색(DFS)

   시작 정점을부터 갈 수 있는 하위 정점까지 가장 깊게 탐색하고, 더이상 갈 곳이 없다면 마지막 갈림길로 돌아와서 다른 정점을 탐색하며 결국 모든 정점을 방문하는 순회 방법

   미로 탐색이라 생각하면 쉽다. 끝까지 가보고 막히면 돌아와서 다른 갈림길로

   • 깊이 우선 탐색의 특징

     • 모든 정점을 방문할 때 유리하다. 따라서 경우의 수, 순열과 조합 문제에서 많이 사용
     • BFS에 비해 코드 구현이 간단하다.

3. DFS의 동작 과정

   1. DFS를 하기 전에 일단 탐색을 진행할 그래프가 필요하다.

      그래프는 인접 행렬 혹은 인접 리스트의 방식으로 표현할 수 있다.

      # 인접 행렬
      graph = [
      	[0, 1, 1, 0, 0, 0, 0],
      	[1, 0, 0, 1, 1, 0, 0],
      	[1, 0, 0, 0, 1, 1, 0],
      	[0, 1, 0, 0, 0, 0, 0],
      	[0, 1, 1, 0, 0, 0, 1],
      	[0, 0, 1, 0, 0, 0, 0],
      	[0, 0, 0, 0, 1, 0, 0]
      ]
            
      # 인접 리스트
      graph = [
      	[1, 2],
      	[0, 3, 4],
      	[0, 4, 5],
      	[1],
      	[1, 2, 6],
      	[2],
      	[4]
      ]
      

   2. 각 정점을 방문했는지 여부를 판별할 체크 리스트 필요

      사람과 달리 컴퓨터는 각 정점에 방문했느지 여부를 알 수 없다.

      visted 리스트를 선언해서 정점 방문 체크 리스트를 만들어 준다.

      visited = [False] * n # n은 정점의 개수
      

      정점i	0	1	2	3	4	5	6
      visited[i]	False	False	False	False	False	False	False

      정점i	0	1	2	3	4	5	6
      visited[i]	True	True	False	True	False	False	False

      방문한 정점은 생략하고 방문하지 않은 정점만 골라서 가게된다.

      정점i	0	1	2	3	4	5	6
      visited[i]	True	True	True	True	True	True	True

      모든 정점을 돌게 되면 종료

4. DFS의 구현 방식

   인접 리스트를 활용한 그래프를 기준으로 설명!

   • 반복문을 이용한 DFS

     DFS는 직전에 방문한 정점으로 차례로 돌아가야 하므로, 후입선출 구조의 스택을 사용

     graph = [
     	[1, 2],
     	[0, 3, 4],
     	[0, 4, 5],
     	[1],
     	[1, 2, 6],
     	[2],
     	[4]
     ]
          
     visited = [False] * n # 방문 처리 리스트 만들기
          
     def dfs(start):
     	stack = [start] # 돌아갈 곳을 기록
     	visited[start] = True # 시작 정점 방문 처리
              
     	while stack: # 스택이 빌 때까지(돌아갈 곳이 없을때까지) 반복
     		cur = stack.pop() # 현재 방문 정점(후입선출)
                  
     		for adj in graph[cur]: # 인접한 모든 정점에 대해
     			if not visited[adj]: # 아직 방문하지 않았다면
     				visited[adj] = True # 방문 처리
     				stack.append(adj) # 스택에 넣기
     dfs(0) # 0번 정점에서 시작
     

5. DFS 문제 풀이

   BOJ 2606-바이러스

   1. 입력 값을 받아 인접 리스트를 생성

      n = int(input()) # 정점 개수(컴퓨터)
      m = int(input()) # 간선 개수(네트워크)
      graph = [[] for _ in range(n + 1)]
      visited = [False] * (n + 1)
      total = 0
            
      # 인접 리스트 만들기
      for _ in range(m):
      	v1, v2 = map(int, input().split())
      	graph[v1].append(v2)
      	graph[v2].append(v1)
                
      # 인접 리스트
      graph = [
      	[],
      	[2, 5],
      	[1, 3, 5],
      	[2], [7],
      	[1, 2, 6],
      	[5],
      	[4]
      ]
      

   2. 1번 컴퓨터를 시작 정점으로 DFS 진행

      visited = [False] * n
            
      def dfs(start):
      	stack = [start]
      	visited[start] = True
                
      	while stack:
      		cur = stack.pop()
                    
      		for adj in graph[cur]:
      			if not visited[adj]:
      				visited[adj] = True
      				stack.append(adj)
      dfs(1) # 1번 정점에서 시작
      

      방문 체크 리스트를 최신화 하며 이동 반복