Algorithm 공부 #13 - 그래프(그래프의 표현)

 

 

Algorithm 공부 #13  - 그래프(그래프의 표현)

 

 

에지 리스트(edge list)

 

  ● 에지를 중심으로 그래프를 표현

  ● 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현

  ● 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현

 

 

인접 행렬(adjacency matrix)

  ● 2차원 배열을 자료구조를 이용하여 그래프를 표현

  ● 노드를 중심으로 그래프를 표현

  ● 노드와 관련되어 있는 에지를 탐색하기 위해서는 N번 접근해야 하므로 시간복잡도가 인접 리스트에 비해 느림

  ● 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐

 

 

인접 리스트(adjacency list)

  ● 2차원 벡터로 그래프를 표현

  ● 구현은 복잡하나 노드와 연결된 에지를 탐색하는 시간이 뛰어나며, 노드 개수가 커도 공간 효율이 좋음

  ● 메모리 초과 에러도 잘 발생하지 않아 코테에서 인접 리스트를 통한 그래프 구현을 선호

 

 

백준 18352번 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

※ 모든 도로의 거리가 1이므로 가중치가 없는 인접 리스트로 구현 가능! ※

● 주어진 출발점에서 bfs탐색

● 탐색 종료 후 방문 배열에서 값이 k와 같은 도시의 번호를 출력

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

vector<vector<int>>A; // 인접 리스트
vector<int>visit; // 방문 여부
vector<int>answer; // 정답 출력
void bfs(int node); // bfs

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, K, X;
	cin >> N >> M >> K >> X;
	A.resize(N + 1); 
	visit.resize(N + 1);
	
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		A[start].push_back(end); // 단방향이므로
	}
	for (int i = 0; i <= N; i++)
		visit[i] = -1; // -1로 초기화
	bfs(X); // 출발지점으로부터 bfs탐색
	for (int i = 0; i <= N; i++) {
		if (visit[i] == K) // 최단 거리가 K인 도시가 있다면
			answer.push_back(i); // 정답 배열에 push
	}
	if (answer.empty()) // 비어있다면 없는 것이므로
		cout << -1; // -1을
	else { // 비어있지 않으면 오름차순
		sort(answer.begin(), answer.end()); // 오름차순 정렬
		for (int i : answer) {
			cout << i << '\n';
		}
	}
}
void bfs(int node) {
	queue<int>myQueue;
	myQueue.push(node);
	visit[node]++;

	while (!myQueue.empty()) {
		int now_node = myQueue.front();
		myQueue.pop();
		for (int i : A[now_node]) {
			if (visit[i] == -1) {
				visit[i] = visit[now_node] + 1;
				myQueue.push(i);
			}
		}
	}
}

 

 

백준 1325번 효율적인 해킹

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

※ 인접 리스트로 구현하고 bfs로 탐색하는 문제 ※

● 모든 node에 대해서 bfs를 탐색하기

● bfs를 탐색하면서 해킹할 수 있는 컴퓨터의 개수를 업데이트 해주기

● answer배열에서 최댓값을 찾고 그 최댓값에 해당하는 컴퓨터의 번호를 출력해주기

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

vector<vector<int>>A;
vector<int>answer;
vector<bool>visit;
void bfs(int node);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	A.resize(N + 1);
	visit.resize(N + 1);
	answer.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		A[start].push_back(end);
	}
		
	for (int i = 0; i <= N; i++) {
		fill(visit.begin(), visit.end(), false);
		bfs(i);
	}
	int max1 = 0;

	for (int i = 1; i <= N; i++) {
		if (max1 < answer[i])
			max1 = answer[i];
	}
	for (int i = 1; i <= N; i++) {
		if (answer[i] == max1)
			cout << i<< '\n';
	}
}
void bfs(int node) {
	queue<int>myQueue;
	myQueue.push(node);
	visit[node] = true;
	while (!myQueue.empty()) {
		int now_node = myQueue.front();
		myQueue.pop();
		for (int i : A[now_node]) {
			if (visit[i] == false) {
				myQueue.push(i);
				answer[i]++;
				visit[i] = true;
			}
		}

	}

}

 

 

 

백준 1707번 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

※ 인접리스트와 dfs를 통해 문제 접근 ※

● 양방향 그래프이므로 start와 end를 입력받고 두 개다 벡터에 푸쉬해주기

● 이분그래프 판단 변수를 지정해놓고 true일 때면 그 node에서 dfs탐색

● 테스트 케이스가 여러 개이므로 각 테스트가 끝날 때마다 배열들 초기화

● dfs탐색에서 인접한 노드는 같은 집합이 아니므로 다른 집합으로 처리

● dfs탐색에서 이미 방문한 노드가 같은 집합이라면 iseven변수를 false로 처리

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

bool isEven;
vector<vector<int>>A;
vector<int>check;
vector<bool>visit;
void dfs(int node);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int V, E;
		cin >> V >> E;
		A.resize(V + 1); // 인접 리스트 크기 
		check.resize(V + 1); // check배열 크기
		visit.resize(V + 1); // 방문배열 크기
		isEven = true; // 이분그래프 판단 여부
		for (int j = 0; j < E; j++) {
			int start, end;
			cin >> start >> end;
			A[start].push_back(end); // 양방향 그래프
			A[end].push_back(start); // 양방향 그래프
		}
		for (int j = 1; j <= V; j++) {
			if (isEven) // 이분 그래프라면 dfs탐색을
				dfs(i);
			else // 아니라면 break
				break;
		}
		if (isEven) // 이분 그래프이므로 yes를
			cout << "YES" << "\n";
		else // 이분 그래프가 아니므로 no를
			cout << "NO" << "\n";
		
		for (int j = 0; j <= V; j++) { // 테스트 케이스만큼 돌려야 하므로 각 배열들 초기화
			A[j].clear();
			check[j] = 0;
			visit[j] = false;
		}
	}
}
void dfs(int node) {
	visit[node] = true;  // node를 true로

	for (int i : A[node]) {
		if (visit[node] == false) {
			check[i] = (check[node] + 1) % 2; // 인접한 노드는 같은 집합이 아니므로
			dfs(i); // 이전 노드와 다른 집합으로 처리
		}
		else if (check[node] == check[i]) // 이미 방문한 노드가 나랑 같다면
			isEven = false;
	}
}