[CH5 DFS/BFS] 탐색 알고리즘 DFS/BFS (1)

DFS

• Depth-First Search, 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 이를 알아보기 전, 먼저 그래프(Graph)의 기본 구조를 알아보자

---

Graph(그래프)

그래프

• 그래프는 노드(Node)와 간선(Edge)로 표현되며, 이 떄 노드를 정점(Vertex)이라고도 말한다
• 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다
• 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다
• 노드에서 노드로 이동하려면 간선을 통해 이동하면 되는것이다!
• 프로그래밍에서 그래픈느 크게 2가지 방식으로 표현할 수 있다
  • 인접 행렬(Adjacency Matirx) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

---

인접 행렬(Adjacency Matrix) 방식

• 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

내가 그린 인접행렬 'ㅅ'

• 위처럼 연결된 그래프를 인접 행렬로 표현하면 파이썬에서는 2차원 리스트로, c++에서는 2차원 배열로 구현할 수 있다
• 연결이 되지 않은 노드끼리는 무한(infinity)의 비용이라고 작성한다
• 이는 실제 코드에서는 999999999, 987654321과 같이 정답이 될 수 없는 큰 수로 초기화한다
• 다음은 인접 행렬을 코드로 구현한 것이다

파이썬 코드)

INF = 999999999

#2차원 리스트로 인접 행렬 표현
graph = [
    [0,7,5],
    [7,0,INF]
    ,[5,INF,0]
    ]
    
print(graph)

파이썬 인접 행렬 결과화면

c++ 코드)

#include <iostream>
#define INF 999999999 

using namespace std;

int main()
{
    int graph[3][3] = {
        {0,7,5},
        {7,0,INF},
        {5,INF,0}
    };
    
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cout<<graph[i][j]<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

c++ 인접 행렬 결과화면

 

---

인접 리스트(Adjacency List) 방식

• 인접 리스트 방식에서는 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다

• 인접 리스트는 '연결 리스트' 자료구조를 이용해 구현하는데, c++나 자바에서는 연결 리스트 기능을 위한 표준 라이브러리를 제공한다
• 반면에 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공한다
• 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 된다!

 

파이썬 코드)

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

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

#노드 1에 연결된 노드 정보 저장(노드, 가중치)
graph[1].append((0,7))

#노드 2에 연결된 노드 정보 저장(노드, 가중치)
graph[2].append((0,5))

print(graph)

파이썬 인접 리스트 결과화면

 

c++ 코드)

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

//행이 3개인 인접 리스트 표현
vector<pair<int,int>> graph[3];

int main()
{
    //노드 0에 연결된 노드 정보 저장 {노드, 가중치}
    graph[0].push_back({1,7});
    graph[0].push_back({2,5});
    
    //노드 1에 연결된 노드 정보 저장 {노드, 가중치}
    graph[1].push_back({0,7});
    
    //노드 2에 연결된 노드 정보 저장 {노드, 가중치}
    graph[2].push_back({0,5});
    
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<graph[i].size();j++)
        {
            printf("(%d, %d) ",graph[i][j].first, graph[i][j].second);
        }
        cout<<'\n';
    }

    return 0;
}

c++ 인접 리스트 결과화면

---

인접 행렬 vs 인접 리스트

1. 메모리 측면
   • 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다
   • 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효욜적으로 사용한다
   • 즉, 메모리 측면에서는 인접 리스트가 유리하다!
2. 속도 측면
   • 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다
   • 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다
   • 즉, 특정 노드의 연결 여부를 확인하는 부분에서는 인접 행렬이 유리하다!
3. 예시) 노드 1과 노드 7이 연결되어 있는 상황을 가정하자
   • 인접 행렬은 graph[1][7]만 확인하면 되는 반면, 인접 리스트는 앞에서부터 차례대로 확인해야 한다
   • 그러므로 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다!

---

 

일단은 내용이 너무 길어지니까 여기까지 정리하고!

DFS와 BFS의 동작 과정은 다음 게시물에 정리하도록 하자!

빠잉!