[알고리즘][DFS와BFS 완전정복] 그래프의 표현

어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다.

백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!!  그래서 나와 같이 알고리즘 문제풀이 새내기 왕초보들을 위해 완전 정복이라는 카테고리로 올리고자 한다.  글을 쓰면서 나도 공부하고, 자료가 부디 도움이 되길 바라는 마음입니다 :)

---

1. 그래프 표현

 

인접 행렬

- 양방향 그래프 일 때 A[i][j], A[j][i]

- 인접 행렬은 없는 간선도 저장하기 때문에 자주 쓰이지는 않는다. 쉬운 문제를 풀 때 주로 사용한다. 

- 인접 행렬의 공간 복잡도는 O(V^2)이다.

 

 

• 가중치가 없는 경우) 

#include <cstdio>
#include <vector>

int a[10][10];
int main(){
          int n,m;
          scanf("%d %d", &n, &m);
          for(int i=0; i<m; i++){
                int u,v;
                scanf("%d %d", &u, &v);
                a[u][v] = 1;
                a[v][u] = 1; //단방향 그래프일때는 필요없다
          }
}

 

• 가중치가 있는 경우)

- 연결된 정보를 가중치 값을 넣어주면된다. A[i][j] = W

#include <cstdio>
#include <vector>

int a[10][10];
int main(){
          int n,m;
          scanf("%d %d", &n, &m);
          for(int i=0; i<m; i++){
                int u,v,w;
                scanf("%d %d %d", &u, &v, &w);
                a[u][v] = w;
                a[v][u] = w
          }
}

 

 

 

 

 

 

 

인접 리스트

 

- 인접 리스트의 공간 복잡도는 O(E) 이다. 

- 대부분의 경우에는 인접 리스트를 사용하여 문제를 푼다. 

- 링크드 리스트를 이용해서 구현한다. 

- A[i] = i와 연결된 정점을 링크드 리스트로 포함하고 있다.

- 링크드 리스트를 사용하는 이유는 필요한 만큼만 공간을 활용하려는 것인데 구현하기에 시간이 오래걸리기 때문에, 주로 c++의 vector나 자바의 arraylist와 같이 길이를 변경할 수 있는 배열을 이용해서 구현한다. 

 

※ 벡터를 사용할 때 주의 할 점

vector<int>  a(10) => 크기가 10인 일차원 배열 int a[10]

vector<int>  a[10]  => 배열을 의미 vector<int> a가 10개 있다는 것

 

 

• 가중치가 없는 경우)

여기서의 숫자는 정점을 나타내는 것이 아니라 간선을 의미한다. 

#include <cstdio>
#include <vector>

using namespace std;
vector<int> a[10];
int main(){
          int n,m;
          scanf("%d %d", &n, &m);
          for(int i=0; i<m; i++){
                int u,v;
                scanf("%d %d", &u, &v);
                a[u].push_back(v);
                a[v].push_back(u);
          }
}

 

 

 

• 가중치가 있는 경우)

- pair를 이용하여 정점과 가중치 정보를 저장한다. 

#include <cstdio>
#include <vector>

using namespace std;
vector<pair<int,int>> a[10];
int main(){
          int n,m;
          scanf("%d %d", &n, &m);
          for(int i=0; i<m; i++){
                int u,v,w;
                scanf("%d %d %d", &u, &v, &w);
                a[u].push_back(make_pair(v,w));
                a[v].push_back(make_pair(u,w));
          }
}

 

 

 

 

 

 

 

간선 리스트

 

- 인접행렬과 인접리스트를 모두 사용할 수 없는 경우에는 간선 리스트 라는 자료구조를 이용하여 그래프를 저장할 수 있다.

- 대부분의 문제는 인접 리스트로 풀리기때문에 간선 리스트를 사용할 일은 사실 많지 않다. 

- 배열을 이용해서 구현한다. 

- 간선을 모두 저장하고 있다. 

- E라는 배열에 간선을 모두 저장한다. 

- O(E)의 공간복잡도를 가진다. 

 

 

 

- 각 간선의 앞 정점을 기준으로 개수를 센다.

                 i   0   1   2   3   4   5  

          cnt[i]  0   2   4   2   4   3  

- 그 다음에는 cnt 배열을 앞에서부터 누적하면서 구한다. cnt[i] = cnt[i-1]+cnt[i]

                 i   0   1   2   3    4    5 

          cnt[i]  0   2   6   8  12  15 

- i번 정점과 연결된 간선은 E배열에서 cnt[i-1]부터 cnt[i]-1 까지이다.

    예) 3번 정점: cnt[2] ~ cnt[3] - 1 = 6 ~ 7

 

 

다음글)

2020/02/29 - [알고리즘/기본기 다지기] - [알고리즘][DFS와BFS 완전정복] 그래프의 탐색

[알고리즘][DFS와BFS 완전정복] 그래프의 탐색