11일차 강의 (24 ~ 26강)

24강 (그래프)

그래프 = 정점과 간선으로 이루어진 자료구조

 

단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

 

표현법 1 - 인접 행렬

방향그래프

int adj_matrix[10][10] = {};

int v, e;

cin >> v >> e;

for (int i  = 0; i < e; ++i) {

  int u, v;

  cin >> u >> v;

  adj_matrix[u][v] = 1;

}

무방향그래프

int adj_matrix[10][10] = {};

int v, e;

cin >> v >> e;

for (int i = 0; i < e; ++i) {

  int u, v;

  cin >> u >> v;

  adj_matrix[u][v] = 1;

  adj_matrix[v][u] = 1;

}

 

표현법 2 - 인접리스트

vector를 가지고 구현

방향그래프

vector<int> adj[10];

int v, e;

cin >> v >> e;

for (int i = 0; i < e; ++i) {

  int u, v;

  cin >> u >> v;

  adj[u].push_back(v);

}

무방향그래프

vector<int> adj[10];

int v, e;

cin >> v >> e;

for (int i = 0; i < e; ++i) {

  int u, v;

  cin >> u >> v;

  adj[u].push_back(v);

  adj[v].push_back(u);

}

 

인접 행렬은 두 점의 연결여부를 자주 확인할 때, E가 V^2에 가까울 때 효율적

인접 리스트는 특정 정점에 연결 모든 정점을 자주 확인할 때, E가 V^2보다 훨씬 작을 때 효율적

 

인접 리스트를 주로 사용

 

비재귀 DFS는 일반적 DFS(재귀 DFS)와 방문 순서가 다르다.

Flood Fill, 순회가 아니라 DFS의 고유적 성질을 사용해 해결해야 할 경우에는 비재귀 코드 사용 불가

→ 재귀방식이 사용 불가능한 상황에서 일반 DFS 성질이 필요한 경우 pop할 때 visited를 체크하는 방식을 사용

(+ pop하자마자 if(vis[cur]) continue를 통해 중복 순회 방지 필요)

 

25강 (트리)

그래프의 특별한 종류임

트리 : 무방향이면서 사이클이 없는 연결 그래프

= 임의의 두 점을 연결하는 simple path(정점이 중복해서 나오지 않는 경로)가 유일한 그래프

= V개의 정점을 가지고 V-1개의 간선을 가지는 연결 그래프

 

트리의 bfs에서는 vis배열을 들고갈 필요가 없이 부모가 누구인지만 저장하고 있으면 됨

vector<int> adj[10];

int p[10];

void bfs (int root) {

  queue<int> q;

  q.push(root);

  while (!q.empty()) {

    int cur = q.front();

    q.pop();

    cout << cur << ' ';

    for (int nxt : adj[cur]) {

      if (p[cur] == nxt) continue;

      q.push(nxt);

      p[nxt] = cur;

    }

  }

}

 

int depth[10];을 추가 선언하고

p[nxt] = cur; 다음에 depth[nxt] = depth[cur] + 1;을 통해 depth를 전부 계산할 수 있다.

 

dfs 재귀구조 사용시 스택메모리 제한 주의하기

 

이진트리 → lc, rc, parent형태의 배열로 표현

int lc[30];

int rc[30];

 

이진 트리의 순회

레벨 순회 (높이 순 방문) → BFS

전위 순회 (preorder) → 재귀 (DFS와 방문 순서가 동일함)

1. 현재 정점을 방문한다

2. 왼쪽 서브트리를 전위 순회

3. 오른쪽 서브 트리를 전위 순회

중위 순회 (inorder) → 재귀, 트리의 모양에서 가장 왼쪽에 있는 것부터 방문 (이진 탐색 트리의 경우 크기 순)

1. 왼쪽 서브트리를 중위 순회

2. 현재 정점을 방문한다

3. 오른쪽 서브 트리를 중 순회

후위 순회 (postorder) → 재귀

1. 왼쪽 서브트리를 후위 순회

2. 오른쪽 서브 트리를 후위 순회

3. 현재 정점을 방문한다

 

26강 (위상 정렬)

위상 정렬 : 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬

하나의 그래프에는 여러 개의 위상 정렬 결과가 있을 수 있음

 

그래프 안에 사이클이 존재할 경우에는 올바른 위상 정렬이 존재할 수 없다

매 순간마다 들어오는 간선이 없는 정점을 제거하는 방식으로 위상 정렬을 구현할 수 있다.

 

구현의 편의를 위한 성질

1. 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소시켜도 과정을 수행 가능

 

2. indegree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가

 

목록은 큐로 관리

O(V+E)로 구현 가능

 

위상 정렬 알고리즘

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채움

2. idegree가 0인 정점들을 모두 큐에 넣음

3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가

4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가

5. 큐가 빌 때 까지 3, 4번 과정을 반복

 

위상정렬 결과에 모든 정점이 포함되어있는지 여부를 확인하여 사이클 여부를 알 수 있다.

 

구현코드 ↓