[Algorithm] 탐색 알고리즘 DFS/BFS

😊 DFS Depth-First Search
깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

프로그래밍에서 그래프를 표현하는 2가지 방식

• 인접 행렬 Adjacency Matrix : 2차원 배열로 그래프의 연결관계를 표현하는 방식
• 인접 리스트 Adjacency List : 리스트로 그래프의 연결 관계를 표현하는 방식

🤭인접행렬 예제

#인접 행렬 방식 예제
INF=999999 #무한의 비용 선언

#2차원 리스트를 이용해 인접행렬 표현
graph = [
    [0,1,2],
    [1,30,INF],
    [5,INF,0]
    ]

print(graph)

🤭인접리스트 예제

graph=[[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((1,5))

print(graph)

🤭DFS 예제

#DFS메서드 정의
def dfs(graph,v,visited): #v가 현재노드
    visited[v]=True #현재노드를 방문처리(True)
    print(v,end=' ')

    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
    ]
#위 그래프 해석 예시 : 0은 아무와도 연결X 1은 2,3,8과 연결

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*9

#정의된 DFS 함수 호출
dfs(graph,1,visited)

😇이해돕기
현재노드: v , visited배열 : 방문한 곳 체크(true) ,graph : 정보담긴 리스트

• dfs
  들어온 노드 (현재노드) true로 방문처리 해주고
  이 노드와 연결된 다른 노드를 재귀적으로 방문하는데 false일때만 재귀

😊 BFS Breadth-First Search
너비 우선 탐색
쉽게 말해서 가까운 노드부터 탐색하는 알고리즘

🌟 DFS vs BFS
DFS 는 최대한 멀리있는 노드를 우선으로 탐색
BFS 는 그 반대

🌟DFS : 스택 이용 / 재귀 함수 이용
🌟BFS : 큐 이용 / 큐 자료구조 이용

🤭DFS 예제
BFS는 선입선출 방식인 큐 자료구조를 이용
먼저 들어온 것이 먼저 나가게되어 가까운 노드부터 탐색을 진행

from collections import deque 

#BFS메서드 정의
def bfs(graph,start,visited): #v가 현재노드
    #큐 구현을 위해 deque라이브러리 사용
    queue=deque([start])

    #현재노드를 방문 처리
    visited[start] = True

    #큐가 빌 때까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v=queue.popleft()
        print(v,end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
    ]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*9

#정의된 DFS 함수 호출
bfs(graph,1,visited)