[알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -2

* 참고: 코딩은 python기준으로 짰습니다. 

 

저번글 ([알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -1 (tistory.com))에서는 DFS와 BFS의 간단한 개념을 살펴보았다. 이번글에서는 아래 두 개를 살펴보자. 

 

1. 두 알고리즘을 사용하기 위한 준비

2. DFS 코딩, 그리고 예시 문제

 

<DFS(깊이 우선 탐색), BFS (너비 우선 탐색) 글 순서>

1.  DFS와 BFS의 간단한 개념 [알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -1 (tistory.com))

2. 두 알고리즘을 사용하기 위한 준비 [이번 글]

3. DFS 코딩, 그리고 예시 문제 [이번 글]

4. BFS코딩, 그리고 예시 문제 

 

두 알고리즘을 사용하기 위한 준비

• 어떤 알고리즘문제에 DFS를 쓰고, 어디에 BFS를 써야할까? 
  • DFS와 BFS: 성질과 사용되는 곳이 매우 다름
  • 둘 중 무엇을 사용해도 괜찮은 경우: 컴포넌트의 개수를 세거나 각 컴포넌트의 크기를 구할 때

 

• 코딩 시 정의해야 하는 변수
  • node, adj 필요
  • node: 그래프의 노드들 정의
  • adj =[[], [], [], []] → edge 연결이 있을 때 필요. programmers “타겟 넘버”처럼 list에 들어있는 순서대로 연결이 되어있으면 필요 없음
• 예시문제:
  • programmers - 단어 변환: 한 번에 끝까지 갈 때는 다시 돌아가면 안 돼서 visited=True 해야 하지만, 한 길이 끝나면, 다시 False로 바꿔야 함 (새로운 길에 나타나기 가능)

 

 

DFS (depth first serach)

• 스택(list in python) 필요 → 최근(시간상 나중)에 방문한 노드들을 봄
• 시간 복잡도: O(V+E) where, V=정점의 개수, E= 간선의 개수
  • 인접 리스트가 없고, 인접 행렬만 있다면, 다음에 방문할 정점을 찾을 때 모든 정점을 순회하며 둘이 이어져 있는지 체크해야 함 → O(V^2)
•  DFS 코드

class Graph:
    def __init__(self, n):
        self.N=n # 정점의 개수
        self.adj = [[] for _ in range(n)]
        self.visited = [False] *n
    def addedge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)
        
    def sortlist(self):
        for i in range(self.N):
            self.adj[i].sort()
            
    def dfs(self, curr):
        self.visited[curr] = True
        for next in self.adj[curr]:
            if not self.visited[next]:
                self.dfs(next)

 

• BFS처럼 거리 구하기 가능 - #백준 2644 촌수계산
• 백준 2644 링크: https://www.acmicpc.net/problem/2644
• 해답

# 트리 탐색하기 문제
def dfs(v, num):
  num += 1
  visited[v] = True

  # 찾아야 하는 사람의 번호를 방문했을 때
  if v == b:
    answer.append(num)

  for i in family[v]:
    if not visited[i]: # 노드 방문
      dfs(i, num)

################################################################
n = int(input()) # 전체 사람의 수
a, b = map(int, input().split()) # 촌수를 계산해야하는 두 사람의 번호 // 다시말해서 시작노드와 도착노드
m = int(input()) # 부모 자식들 간의 관계의 개수
family = [[] for _ in range(n + 1)] # 부모 - 자식 2차원 배열
visited = [False] * (n + 1)
answer = []

for _ in range(m):
  x, y = map(int, input().split()) # 부모 자식간의 관계를 나타내는 두 번호
  family[x].append(y)
  family[y].append(x)
################################################################


dfs(a, 0)

if len(answer) == 0: # 친척 관계 아닐때
  print(-1)
else:
  print(answer[0] - 1)

 

• DFS를 재귀로 사용하기  -> componenet 셀 때!
  • ex. 백준 11724 (링크: https://www.acmicpc.net/problem/11724)
  • 해답

# 연결 요소의 개수 - dfs
# input 받기
import sys
class Graph:
    def __init__(self, n):
        self.N=n # 정점의 개수
        self.adj = [[] for _ in range(n)]
        self.visited = [False] *n
    def addedge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)
        
    def sortlist(self):
        for i in range(self.N):
            self.adj[i].sort()
            
    def dfs(self, curr):
        self.visited[curr] = True
        for next in self.adj[curr]:
            if not self.visited[next]:
                self.dfs(next)
    
    def dfsall(self):
        components =0
        self.visited = [False]*self.N
        for i in range(self.N):
            if not self.visited[i]:
                self.dfs(i)
                components+=1
        return components
    
# 명령 개수 받아오기
#sys.stdin=open("./input.txt","r")
v, e = map(int, sys.stdin.readline().split())
a = Graph(v)
for i in range(e):
    start, end   = map(int, sys.stdin.readline().split())
    a.addedge(start-1,end-1)
a.sortlist()
print(a.dfsall())