DFS/BFS

<이것이 취업을 위한 코딩테스트다>를 공부하며 정리한 내용입니다.

용어 정의

• 탐색 : 많은 양의 데이터 중 원하는 데이터를 찾는 과정
• 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
• 스택(stack) : 선입후출 / 후입선출 ⇒ (Python) 리스트 구조만 이용하면 됨. append()&pop() 메소드
• 큐(queue) : 선입선출 ⇒ (Python) from collections import deque / queue=deque() 이용하기 (deque가 queue보다 효율적) ⇒ append() & popleft() 메소드
  
• 재귀 함수 : 자기 자신을 다시 호출하는 함수
  

#팩토리얼 예제
    
#반복문 ver
def factorial_iterative(n):
    result=1
    for i in range(2,n+1):
        result*=i
            
    return result
    
#재귀함수 ver
def factorial_recursive(n):
    if n<=1:
        return 1
    
    return n*factorial_recursive(n-1)
    
print('반복문 버전: ',factorial_iterative(5))
print('재귀함수 버전: ', factorial_recursive(5))

⇒ 재귀함수의 코드가 더 간결하다. 점화식을 그대로 사용함!!!!!!!

DFS(Depth-First Search)

깊이 우선 탐색, 최대한 멀리 있는 노드를 우선으로 탐색(pop!) ❤ 스택(리스트)

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 (연결되지 않는것은 ‘무한’으로 표시)

  	0	1	2
  0	0	7	5
  1	7	0	무한
  2	5	무한	0

INF=999999999 #무한의 비용 선언
        
#2차원 리스트를 이용해 인접 행렬 표현
graph= [
     	[0, 7, 5],
        [7, 0, INF],
        [5, INF, 0],
       ]
        
print(graph) #[[0, 7, 5],[7, 0, 999999999],[5, 999999999, 0]]

• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식. 각 노드별로 (연결된 노드 인덱스, 비용) 값 가짐.
  

graph = [[] for _ in range(3)]
        
graph[0].append((1,7))
graph[0].append((2,5))
        
graph[1].append((0,7))
graph[2].append((0,5))
        
print(graph) #[[(1,7),(2,5)],[(0,7)],[(0,5)]]

⇒ 인접 행렬 vs 인접 리스트

	인접 행렬	인접 리스트
메모리	모든 관계를 저장 → 불필요한 낭비 있음.	연결된 정보만 저장→ 효율적 사용
탐색 속도 (두 노드 연결관계)	필요한 두 노드 인덱스만 알면 바로 찾을 수 있음. → 빠름	연결되어 있는지 확인하려면 그 행에 가서 하나씩 확인해야함. → 느림

• 코드
  • 재귀함수 이용!
  • 실제로 집어넣고, 빼는 행동은 하지 않음. 방문했다는걸로 퉁침.
    

#DFS 메소드 정의
def dfs(graph, v, visited):
    visited[v]=True #방문 표시
    print(v, end=' ') #출력
            
    for i in graph[v]: #하나의 노드와 연결되어 있는 것 모두 꺼내기
        if not visited[i]: #방문한 적이 없다면
            dfs(graph,i,visited) #지금 방문해보자 (인내심 부족)
        
# 인접 행렬
graph=[
        [],
        [2,3,8],
        [1,7],
        [1,4,5],
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7]
      ]
        
visited=[False]*9 #리스트 요소는 9개. 실질적으로는 1-8 인덱스만 사용
        
dfs(graph, 1, visited) #1 2 7 6 8 3 4 5

BFS(Breath First Search)

너비 우선 탐색, 최대한 가까이 있는 노드를 우선 탐색 ❤ 큐

• 코드
  - 큐 자료구조 이용
  - 실제로 popleft()와 append()로 빼거나 집어넣기함.

from collections import deque

#재귀함수 사용 x
#BFS 메소드 정의
def bfs(graph, start, visited):
    #시작 노드 넣어주기
    queue=deque([start])
    visited[start]=True #방문 표시

    while queue:#큐가 비어있을 때까지 반복
        #현재 맨 앞 노드 pop하기
        v=queue.popleft()
        print(v, end=' ')
        #pop한 노드와 연결된 노드 중 방문하지 않았던 노드 모두 넣기
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

# 인접 행렬
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited=[False]*9 #리스트 요소는 9개. 실질적으로는 1-8 인덱스만 사용

bfs(graph, 1, visited)