그래프(Graph)

그래프는 용어가 많고 중요한 만큼 용어 개념을 확실히 정리해야 한다.

 

1. 그래프의 개념

먼저 그래프의 개념은, 일련의 노드(node, vertex, 정점, 꼭지점)V와 엣지(edge, 간선, 변) E로 구성된 자료구조이다. 이러한 그래프의 정보는 정점과 정점 간의 간선이 어떻게 연결되어 구성이 되어있는지의 정보도 포함된 형태를 뜻한다.

 

그래프에서 경로(path)란 노드들의 나열로 구성된 묶음을 뜻한다. 일종의 시퀀스로, 노드들의 간선을 따라 하나의 경로를 구성하게 된다. 이 때 Edge가 겹치지 않게 되면 단순 경로(Simple path)라고 일컫는다.

위의 이미지의 경우 v1-v2-v3-v4-v5 와 같이 v1~v5로 가는 path를 나열할 수 있다.

사이클의 경우에는 경로 중에서 출발점과 도착점이 같은 경우를 말하고 그 중에서도 Edge를 중복하지 않는다면 단순 사이클(Simple Cycle)이라고 할 수 있다.

2. 그래프의 추가 성질

1) 그래프에는 방향성이 있을 수 있다(방향그래프/ 무방향 그래프)

2) 두 정점 사이에 간선이 여러 개도 가능하다

3) 간선에는 가중치가 존재 A->B 이동 거리, 비용 등(가중치 없는 경우 1로 생각)
4) 차수는 정점과 연결되어 있는 간선의 수(방향 그래프의 경우 In-degree, out-degree 구분된다)

 

3. 그래프의 표현

가중치가 없는 방향 그래프(인접행렬 표현)

가중치가 있는 방향 그래프(인접리스트 표현)

그래프에서는 간선의 정보를 어떻게 담아 표현할 것인지가 중요한 요소이다.
간선 -> 어떤 정점 X와 연결된 간선을 어떻게 효율적으로 저장해서 그래프를 표현할 수 있을까?

인접 행렬 -> 이차원 배열을 통해 표현(연결된 경우 A[i][j] =1, 연결이 안된 경우 A[i][j]=0)
인접 리스트 -> 리스트 배열을 통해 각 리스트에서 연결된 정점을 표현(링크드 리스트로 표현한다, 동적으로 길이를 변경할 수 있어야 하므로)

공간 복잡도
인접 행렬 O(V^2) -> 언제 쓰는가 하면, 두 정점간 간선 존재하는지 확인 O(1) 
인접 리스트 O(E) -> 다 살펴본 뒤에 확인해야함

대부분의 경우는 인접 리스트가 좋다.
그럼에도 불구하고 인접 행렬 사용하는 경우

1) 두 정점이 연결되있는지(간선이 존재하는지) 확인하는데 O(1)
2) 두 간선의 역방향 간선이 존재하는 지 확인하는데 O(1)
3) 완전그래프 - 모든 그래프가 연결되있는 경우

이 외의 대부분의 경우는 인접 리스트 사용
간선 리스트라는 개념도 존재(참고만하기)

 

1. ABCDE

문제 : https://www.acmicpc.net/problem/13023

13023번: ABCDE

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#define MAX 2000
using namespace std;
vector<bool> check(MAX);
vector<vector<int>> graph;
int N, M;
int start,fin;

void dfs(int,int);

int main() {
	cin >> N >> M; // 입력받기
	graph.assign(N, vector<int>(0, 0));

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	// DFS 체크
	for (int i = 0; i < N - 1; i++) {
		check.assign(N, false);

		fin = 0;
		dfs(i,1);
		
		if (fin == 1) {
			cout << "1";
			return 0;
		}
	}
	cout << "0";

	return 0;
}

void dfs(int idx, int cnt) {
	check[idx] = true; //탐색

	// 답을 찾았으면
	if (cnt == 5)
		fin = 1;

	// 종료
	if (fin == 1)
		return;

	for (int i = 0; i < graph[idx].size(); i++) {
		int j = graph[idx][i];
		if (check[j] == false)
			dfs(j,cnt+1);
	}
	check[idx] = false;
}