.jpg)
그래프
정점(Vertex, Node)와 간선(Edge)을 통해 표현한다.
G = (V,E)로 나타낸다.
경로 - 단순히 한 정점에서 다른 정점으로 가는 길
사이클 - 특정 정점에서 시작해 다시 그 정점으로 돌아오는 경로
단순 경로와 단순 사이클 - 같은 정점을 두 번 이상 방문하지 않는다.
방향이 있는 그래프와 방향이 없는 그래프가 있다.
방향이 없는 그래프의 경우 양방향 그래프라고도 한다.
두 정점 사이에 간선이 여러개일 수 있다.
루프 - 간선의 양 끝 점이 같은 경우
가중치 - 간선에 가중치가 있는 경우가 있다. 없는 경우 모든 가중치를 1로 생각한다.
차수(Degree) - 정점과 연결되어 있는 간선의 개수
In-degree : 들어오는 간선, Out-degree : 나가는 간선
인접 행렬(Adjacency-matrix) - 정점의 개수가 v개 일 때, v x v 크기의 이차원 배열 사용
A[i][j] = 1 (i -> j) 간선이 있는 경우, 0 없는 경우
인접 리스트 - A[i] = i와 연결된 정점을 리스트로 포함하고 있음
A[1] : 2, 5 - 1에서 2와 5로 연결
리스트는 크기를 동적으로 변경할 수 있어야 하기 때문에, 링크드 리스트나 벡터를 사용한다.
A1 (5,7) : 1 -> 2로 가중치 2, 1 -> 5로 가중치 7
공간 복잡도의 경우 인접 행렬을 사용하는 경우 O(v^2), 인접 리스트의 경우 O(E)에 해당한다.
E가 v^2에 비해 매우 작기 때문에 공간 복잡도에 한해 인접 리스트가 유리하다.
간선 리스트 - 즐겨 사용하진 않으므로 넘어간다.
탐색
DFS - 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아간다.
BFS - 큐를 이용해서 지금 위치에서 갈 수 있는 모든 정점을 큐에 넣는 방식이다. 넣는 동시에
방문 체크
https://www.acmicpc.net/problem/1260
DFS와 BFS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<int> a[1001];
bool check[1001];
void dfs(int node) {
check[node] = true;
cout << node << ' ';
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
dfs(next);
}
}
}
void bfs(int start) {
queue<int> q;
memset(check, false, sizeof(check));
check[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << ' ';
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
check[next] = true;
q.push(next);
}
}
}
}
int main() {
int n, m, start;
cin >> n >> m >> start;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(a[i].begin(), a[i].end());
}
dfs(start);
cout << '\n';
bfs(start);
cout << '\n';
return 0;
}연결 요소(Connected Component)
그래프가 여러개 나누어진 경우 각각의 그래프를 연결 요소라고 한다.
연결 요소에 속한 모든 정점은 연결되어 있으며, 다른 연결 요소에 연결되면 안된다.
연결 요소를 구하는 것은 DFS나 BFS 탐색을 통해 구할 수 있다.
https://www.acmicpc.net/problem/11724
연결 요소의 개수
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<int> a[1001];
bool check[1001];
void dfs(int node) {
check[node] = true;
//cout << node << ' ';
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
dfs(next);
}
}
}
void bfs(int start) {
queue<int> q;
check[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
//cout << node << ' ';
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
check[next] = true;
q.push(next);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
memset(check, false, sizeof(check));
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(a[i].begin(), a[i].end());
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (check[i]) continue;
bfs(i);
cnt += 1;
}
cout << cnt << '\n';
return 0;
}bfs가 더 빠르다.
이분 그래프
A와 B그룹으로 나누었을 때, A에 포함되어 있는 정점끼리 연결된 간선이 없고, B에 포함되어 있는 정점끼리 연결된 간선이 없는 경우, 즉, 모든 간선의 한 끝점은 A에 다른 끝 점은 B에 있는 경우
이분 그래프라고 한다.
그래프를 DFS 또는 BFS 탐색으로 이분 그래프를 확인할 수 있다.
https://www.acmicpc.net/problem/1707
이분 그래프
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<int> a[20001];
int check[20001];
void dfs(int node, int color) {
check[node] = color;
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == 0) {
dfs(next, 3 - color);
}
}
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
a[i].clear();
check[i] = 0;
}
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (check[i] == 0) {
dfs(i, 1);
}
}
bool ans = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < a[i].size(); j++) {
if (check[i] == check[a[i][j]])
ans = false;
}
}
if (ans) {
cout << "YES" << '\n';
}
else {
cout << "NO" << '\n';
}
}
return 0;
}check를 int형으로 썼네.
플러드 필
어떤 위치와 연결된 모든 위치를 찾는 알고리즘을 말한다.
https://www.acmicpc.net/problem/2667
단지번호 붙이기
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
bool check[25][25];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
int n;
int bfs(int y, int x) {
queue<pair<int, int>> q;
check[y][x] = true;
int count = 1;
q.push(make_pair(y, x));
while (!q.empty()) {
pair<int, int> node = q.front();
q.pop();
int nexy;
int nexx;
for (int i = 0; i < 4; i++) {
nexy = node.first + dy[i];
nexx = node.second + dx[i];
if (nexy < 0 || nexy >= n || nexx < 0 || nexx >= n) continue;
if (check[nexy][nexx] == false) {
count += 1;
check[nexy][nexx] = true;
q.push(make_pair(nexy, nexx));
}
}
}
return count;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int k;
scanf("%1d", &k);
if (k == 0) check[i][j] = true;
else check[i][j] = false;
}
}
int cnt = 0;
vector<int> ans;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j] == false) {
ans.push_back(bfs(i, j));
cnt += 1;
}
}
}
sort(ans.begin(), ans.end());
cout << cnt << '\n';
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << '\n';
}
return 0;
}1 글자씩 끊어서 받을 때, scanf
https://www.acmicpc.net/problem/4963
섬의 개수
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int check[50][50];
int dx[] = { 0, 0, -1, 1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int w, h;
void bfs(int y, int x) {
queue<pair<int, int>> q;
check[y][x] = true;
q.push(make_pair(y, x));
while (!q.empty()) {
pair<int, int> node = q.front();
q.pop();
int nexy;
int nexx;
for (int i = 0; i < 8; i++) {
nexy = node.first + dy[i];
nexx = node.second + dx[i];
if (nexy < 0 || nexy >= h || nexx < 0 || nexx >= w) continue;
if (check[nexy][nexx] == 1) {
check[nexy][nexx] = 0;
q.push(make_pair(nexy, nexx));
}
}
}
}
int main() {
while (true) {
cin >> w >> h;
if (w == 0 && h == 0) break;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
scanf("%1d", &check[i][j]);
}
}
int cnt = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (check[i][j] == 1) {
bfs(i, j);
cnt += 1;
}
}
}
cout << cnt << '\n';
}
return 0;
}.jpg)