✅탐색 알고리즘

📌DFS

• Depth-First Search = 깊이 우선 탐색, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

  • 선행으로 알아야 하는 것

    • 1. 그래프의 구조 (노드,간선)
    • 2. 그래프의 표현방식
      • 1. 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현하는 방식
        • 노드의 개수가 많으면 메모리가 불필요하게 낭비된다. 하지만 탐색속도가 빠르다
      • 2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
        • 메모리를 효율적으로 사용하지만, 두 노드가 연결되어있는지에 관한 정보를 얻는 속도가 느림

인접 행렬 방식

INF = int(1e9)
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

• 2차원 리스트를 이용하여 표현한 방식

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

• (0,1) =7 그리고 (1,0)=7

  • 노드0과 노드1은 연결되어있고 가중치가 7이다

• (0,2) = 5 그리고 (2,0) = 5

  • 노드0과 노드2는 연결되어있고 가중치가 5이다

• (2,1) = INF 그리고 (1,2) = INF

  • 노드1과 노드2는 연결되어있지 않다

인접 리스트 방식

# 행이 3개인 2차원 리스트
graph = [[] for _ in range(3)]

# graph[n].append((a,g)) : 노드n와 노드a는 연결되어있고 가중치가 g이다.
graph[0].append((1, 7))
graph[0].append((2, 5))
graph[1].append((0, 7))
graph[2].append((0, 5))

구체적 동작 과정 (스택, 재귀 함수 이용)

1. 탐색 시작 노드를 스택에 삽입하고 방문처리함
2. 스택의 최상단 노드와 연결된 인접노드중, 아직 방문하지 않은 인접노드가 있다면 -> 그것(1개)을 스택에 넣고 방문처리한다. 없다면 -> 스택에서 최상단 노드를 꺼낸다
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다

• 코드

def dfs(graph, v, visited):
    # 노드v를 방문처리
    visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


# 2차원 리스트로 표현된 노드 정보
# 1번째 원소 = [2,3,8] : 노드1과 연결된 노드2,노드3,노드8
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
visited = [False] * 9

dfs(graph, 1, visited)

📌BFS

• Breadth-First Search : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
  • 선행으로 알아야 할 것 : 큐 자료구조(선입선출)
• 보통 DFS보다 BFS가 더 빠르게 동작한다

구체적인 동작 과정 (큐, 큐 자료구조 이용)

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입하고, 방문처리한다
3. 2번의 과정을 더이상 수행할 수 없을 떄까지 반복한다.

• 코드

from collections import deque


def bsf(graph, start, visited):
    # 큐에 start노드를 집어 넣는다
    queue = deque([start])
    # start노드를 방문처리한다
    visited[start] = True
    while queue:
        # 큐에서 노드를 꺼낸다
        now = queue.popleft()
        # 꺼낸 노드를 출력한다 : 방문처리할때 출력해도 무관하지만, 이 방법이 더 간결
        print(now, end=" ")
        for i in graph[now]:
            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
bsf(graph, 1, visited)