4편 그래프 : dfs 1

1. 그래프 표현과 정의

1) 그래프의 정의와 종류

- G(V, E)로 정점(Vertex)과 간선(Edge)의 집합으로 구성된 자료구조

- 속성에 따른 분류

  방향 그래프(directed graph) / 무향 그래프(undirected graph) / 가중치 그래프(weighted graph)

- 형태에 따른 분류

  다중 그래프(multigraph) : 정점들 간에 두 개 이상의 간선이 있을 수 있는 그래프

  단순 그래프(simple graph) : 정점간 최대 한 개의 간선만 있는 그래프

  트리 혹은 루트 없는 트리(unrooted tree) : 부모자식 관계가 없을 뿐 형태는 무향 그래프

  이분 그래프(bipartite graph) : 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에 간선을 갖는 그래프

- 두 가지 이상의 속성을 가질 수 있음

  방향 가중치 그래프 / 이분 가중치 그래프 / 사이클이 없는 방향 그래프(Directed Acyclic Graph : DAG) = 의존 그래프

2) 암시적 그래프 구조들

- 그래프 같은 형태를 갖는 구조가 아니라도 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제

  서로 의존 관계를 갖는 그래프에서 순서를 결정하는 위상 정렬, 의존 그래프는 사이클이 없음(DAG)

  그래프의 크기는 아주 큰데 실제로는 그 중 일부만 사용 : 15-퍼즐

  2^N

3) 그래프의 표현 방법

- 그래프는 트리에 비해 훨씬 정적인 용도로 사용

※ 정적? : 새로운 정점이나 간선을 추가, 삭제 하는 경우가 적은 것

  그래프는 정적이므로 구조의 변경이 어렵더라도 메모리를 적게 차지하는 방법으로 구현함

- 간선의 정보를 어떤 식으로 저장하느냐에 따라 두 가지로 나눔

  인접 리스트 표현(adjacency list) : 그래프의 각 정점마다 해당 정점에서 나가는 간서의 목록을 저장해서 그래프를 표현

vector<list<int>> adj;

  인접 행렬 표현(adjacency matrix) : 2차원 배열을 이용하여 간선의 정보를 저장

vector<vector<bool>> adj;
bool adj[v][v];

- 인접 리스트와 인접 행렬 비교

                     특정 간선을 찾기 위한 탐색 시간         공간

인접 리스트                      V * V                            V+E

인접 행렬                           1                              V * V

※ 벡터 생성자 : 테케 여러개 돌려야 하는 경우에 초기화를 따로 해줄 필요가 없어서 좋음

vector<int> a;
vector<vector<int>> b;

a = vector<int>(할당 갯수, 초기값);
b = vector<vector<int>>(26, vector<int>(26, 0));

  

2. DFS

1) DFS ?

- 탐색 알고리즘 중 하나

- 깊이 우선 탐색

- 시간복잡도

  인접리스트 : 정점의 수 V + 간선의 수 E = O(|V| + |E|)

  인접행렬    : 정점의 수 V * 정점의 수 V = O(|V|^2)

2) dfs의 예제

- 두 정점이 서로 연결되어 있는가 확인

- 연결된 부분집합의 개수 세기

- 위상정렬 : dfs가 종료될 때 저장, 결과를 뒤집으면 위상정렬

                문제를 풀때는 사이클이 생성될 가능성이 있는 그래프는 위상정렬된 결과가 사이클을 갖는지 확인해줘야 함.

예제. 문제 : DICTIONARY

https://algospot.com/judge/problem/read/DICTIONARY

1, 2) 문제를 읽고 이해하기 및 재정의

- 어떤 고대사전에 단어가 적혀있는데 순서가 그 시대의 사전순

- 단어 목록이 주어 질 때, 알파벳 간의 상대적 순서를 출력

- 단어의 수 : 1 <= n <= 1,000

- 각 단어의 길이 : 1 <= L <= 20

- 순서에 모순이 있다면 "INVALID HYPOTESIS" 출력

- 없다면 알파벳 순서를 출력

3) 계획 세우기

- 단어에서 알파벳 간의 순서도 즉, 그래프를 만듦

- dfs로 그래프를 돌면서 가장 깊이 들어가는 알파벳이 순서상으로 가장 뒤이므로

  dfs가 끝날때 마다 알파벳을 추가

4) 계획 검증하기

- 시간복잡도 : 1000개의 단어 입력 시간 + => 싱크맞추는거 없이 cin 쓰면 오래 걸리지만 시간 초과 나진 않을 것 같음

                   그래프 생성시간 +            => 모든 단어를 다 봐야하므로 NL

                   위상정렬 시간 +               => 각 알파벳을 한번씩만 방문하면 되므로 26

                   사이클 검사 시간              => 한 알파벳이 사이클을 생성하는지 확인해야 하므로 26 * 26

  => O(NL)

5, 6) 계획 수행하기 및 회고하기

- 처음에 예제출력 결과를 이해하지 못해서 "위상정렬된 알파벳 + 위상정렬에 사용되지 않은 알파벳" 을 출력함.

  => ogklh abcdefijmnpqrstuvwxyz 무조건 이런식으로만 출력해야 되는지 암.

- 알고보니 그럴필요 없이 그래프를 만들고 있는 알파벳 간의 순서만 정렬하면 됨.

  zyxwvutsrqp  o  nmji  gklh  fedcba  이렇게 그래프를 형성하고 있지 않은 단어들은 순서가 상관없음. ogklh만 순서가 맞으면 됨.

- 그래서 처음에는 그래프를 이루고 있는 알파벳들만 dfs 재귀를 돌림

- 나중에는 그래프를 이루고 있지 않은 알파벳들은 순서가 상관없으므로 모든 알파벳을 dfs 재귀 돌림

- 위상정렬 결과가 사이클을 가지는지 하나씩 확인해봐야 하나???? 으흠...

- dfs를 돌리면서 사이클을 가지는지 확인하기에는 이전 루트를 다 기억하면서 비교해야 하므로 으흠...

- 배열을 하나 만들어서 dfs가 끝나는 시점에 해당 정점이 끝났다는 표시를 해줌.

  방문은 했지만, 끝나지 않은 정점을 방문한 경우 역방향 간선 즉, 사이클

  bool check[n], end[n];

  void dfs(int c){

     check[c] = true;

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

         if(!check[i])

              dfs(i);

         else if(!end[i])

              // cycle

     }

     end[c] = true;

     // 위상정렬 추가

  }

소스코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int t, n;
vector<char> ans;
vector<bool> check;
vector<vector<int> > graph;

int min(int a, int b){
	return ((a < b) ? a : b);
}

bool make_cycle(){
	for (int i = 0; i < (int)ans.size() - 1; i++)
		for (int j = i + 1; j < ans.size(); j++)
			if (graph[ans[i] - 'a'][ans[j] - 'a'])
				return true;
	return false;
}

void dfs(int node){
	check[node] = true;

	for (int i = 0; i < 26; i++)
		if (!check[i] && graph[node][i])
			dfs(i);

	ans.push_back((char)(node + 'a'));
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		vector<string> temp(n);
		// 정점의 갯수를 정확하게 알 수 없기에 알파벳 갯수인 26개로 잡음.
		graph = vector<vector<int> >(26, vector<int>(26, 0));
		check = vector<bool>(26, false);
		for (int i = 0; i < n; i++)
			cin >> temp[i];

		// make graph
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < min(temp[i].size(), temp[i + 1].size()); j++)
				if (temp[i][j] != temp[i + 1][j]){
					graph[temp[i][j] - 'a'][temp[i + 1][j] - 'a'] = 1;
					break;
				}

		// make topolgotical sorting
		for (int i = 0; i < 26; i++)
			if (!check[i])
				dfs(i);

		// 위상정렬 결과에 사이클이 있는가?
		if (make_cycle()){
			cout << "INVALID HYPOTHESIS";
		}
		else{
			for (int i = ans.size(); i > 0; i--)
				cout << ans[i - 1];
		}
		cout << "\n";

		ans.clear();
	}
	return 0;
}

- 알고리즘 문제 해결전략 2편 중 -

- 저작권 문제시 삭제하겠습니다 -