4.1 Graph
4.1-1 그래프
Def) 그래프(Graph)
개체 간의 연결 관계를 표현할 수 있는 비선형 자료구조
ex. 도시들 간의 연결, 지하철 노선도, SNS 친구 관계도 등
Note) 결국 트리는 그래프의 한 종류이다.
즉, 트리를 추상화하면 그래프가 됨.
Note) 그래프의 구성 요소
- 그래프 G = (V, E)
- 정점 V(Vertex, Node)
그래프를 구성하는 기본 단위. 노드.
데이터를 저장하거나 상태를 표현
- 엣지 E(Edge, Link)
정점과 정점을 잇는 선. 간선.
방향을 가질 수도 있음.
가중치(Weight)를 가질 수도 있음.
Note) 그래프 관련 용어
| 가중치(Weight) | 엣지에 부여된 수치. 비용(Cost) |
| 인접 정점(Adjacent Vertex) | 엣지로 연결되어 있는 정점 |
| 차수(Degree) | 정점에 연결된 다른 정점의 개수 |
| 경로(Path) | - 특정 정점에서 다른 정점으로 이동하는 방법을 인접 정점의 나열로 표현한 것. - 경로 상에 특정 정점이 중복되지 않는 경로를 단순 경로(Simple Path)라 함. |
| 사이클(Cycle) | 시작 정점과 마지막 정점이 같은 단순 경로. 즉, 트리는 사이클이 없는 그래프라 할 수 있음. |
| 방향 그래프(Directed Graph) | - 엣지에 방향이 있는 그래프. == 유향 그래프, 네트워크(Network) - 방향 그래프에서 엣지(u, v)는 정점 u에서 정점 v로 이동하는 엣지를 나타냄. 단, (u, v) != (v, u) |
| 가중치 그래프(Weighted Graph) | 엣지에 가중치가 부여되어 있는 그래프 |
| 서브 그래프(Sub-Graph) | 주어진 그래프에서 정점과 간선 일부를 제외하여 만든 그래프. 부분 그래프. |
Def) 인접 행렬
- 정점 갯수가 N인 경우, N by N 크기의 2차원 행렬로
정점의 인접 관계를 표현하는 방법
- adj[u][v]: 노드 u에서 노드 v로 가는 간선이 있다면 1, 없다면 0
- 그래프 정점 개수가 적고, 엣지가 많을 때 유리.
정점 개수가 많을 수록, 엣지가 적을수록 공간이 낭비되게 됨.
공간 복잡도는 O(N^2)
4.1-2 그래프와 인접행렬
Note) 무방향 그래프의 인접 행렬
두 정점이 연결되었음만 표시하는 그래프.
무방향 그래프의 경우, 대각원소를 기준으로
서로 대칭인 형태의 인접 행렬이 만들어짐.
<hide/>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> AdjacentMatrix;
int V;
int E;
int main(void)
{
std::cin >> V >> E;
AdjacentMatrix.assign(V + 1, std::vector<int>(V + 1, 0));
for (int i = 1; i <= E; ++i)
{
size_t Vertex1, Vertex2;
std::cin >> Vertex1 >> Vertex2;
AdjacentMatrix[Vertex1][Vertex2] = AdjacentMatrix[Vertex2][Vertex1] = 1;
}
for (size_t i = 1; i <= V; ++i)
{
for (size_t j = 1; j <= V; ++j)
{
std::cout << AdjacentMatrix[i][j] << ' ';
}
std::cout << std::endl;
}
return 0;
}
Ex) 다음 그림을 보고, 인접행렬을 출력하시오.
입력값을 적어두었으나, 그림과 무방향 그래프 템플릿 코드를 보고도 작성할 수 있으니
되도록 본인이 작성하도록 하시오.
<hide/>
// 입력값
7
6
1 2
1 3
2 4
2 5
3 6
3 7
Note) 방향 그래프의 인접 행렬
두 정점이 연결 되었으나, 연결된 방향까지 고려된 그래프.
<hide/>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> AdjacentMatrix;
int V;
int E;
int main(void)
{
std::cin >> V >> E;
AdjacentMatrix.assign(V + 1, std::vector<int>(V + 1, 0));
for (int i = 1; i <= E; ++i)
{
size_t Vertex1, Vertex2;
std::cin >> Vertex1 >> Vertex2;
AdjacentMatrix[Vertex1][Vertex2] = 1;
}
for (size_t i = 1; i <= V; ++i)
{
for (size_t j = 1; j <= V; ++j)
{
std::cout << AdjacentMatrix[i][j] << ' ';
}
std::cout << std::endl;
}
return 0;
}
Ex) 다음 그래프의 인접 행렬을 출력하시오.
마찬가지로, 입력값 또한 코드와 그래프를 보고 유추하시오.
<hide/>
// 입력값
6
6
A B
B C
B E
E F
E D
D B
Note) 가중치 그래프의 인접 행렬
두 정점이 연결 되었고, 연결된 방향은 물론 가중치까지 고려된 그래프
<hide/>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> AdjacentMatrix;
int V;
int E;
int main(void)
{
std::cin >> V >> E;
AdjacentMatrix.assign(V + 1, std::vector<int>(V + 1, 0));
for (int i = 1; i <= E; ++i)
{
size_t Vertex1, Vertex2;
int Weight;
std::cin >> Vertex1 >> Vertex2 >> Weight;
AdjacentMatrix[Vertex1][Vertex2] = Weight;
}
for (size_t i = 1; i <= V; ++i)
{
for (size_t j = 1; j <= V; ++j)
{
std::cout << AdjacentMatrix[i][j] << ' ';
}
std::cout << std::endl;
}
return 0;
}
Ex) 다음 그래프의 입력 값을 예상해보고, 인접행렬을 출력하시오.
<hide/>
// 입력값
4
5
1 2 6
1 3 2
2 4 1
3 2 3
3 4 5
Def) 인접 리스트
- 각 정점에 인접한 정점들을 연결 리스트로 구현하는 방법
- 보통 정점 개수에 해당하는 배열의 각 원소에
연결 리스트가 속해 있는 형태로 구현
- 정점 갯수가 N이고, 엣지 갯수가 M일 때,
공간 복잡도는 O(N + M).
Note) 무방향 그래프와 방향 그래프의 인접 리스트
- 무방향 그래프의 경우, 공간 복잡도는 O(2M)
- 방향 그래프의 경우, 공간 복잡도는 O(M)
Def) 엣지 리스트
- 모든 엣지 (u, v)를 연결 리스트 또는 배열로 구현하는 방법
- 엣지의 개수가 M일 때, 공간 복잡도는 O(M)
4.2 DFS & BFS
Def) 그래프 순회(Graph Traversal)
- 트리에서도 순회가 있듯, 당연하게도 그래프에도 순회가 있음.
- 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업
- 많은 문제들이 그래프 순회를 이용하여 해결될 수 있음.
ex. 두 정점 사이의 연결 경로가 있는지 검사, 최단 거리 검사 등등
- 대표적인 그래프 순회 방법으로는
깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search)
- 게임에서 쓰이는 길찾기 알고리듬은 다음과 같이 빌드업 가능.
우수법 -> 스택활용 -> DFS -> BFS -> Dijkstra -> A* ...
DFS를 길찾기에 쓸 순 있지만, "최단거리"인지는 알 수 없음에 유의.
BFS는 최단거리까지 고려하여 작성됨.
Dijkstra는 여기에 가중치(비용) 그래프까지 고려하여 작성됨.
A*는 사람처럼 편향을 고려하여 작성됨. (ex. 목적지까지 대각선으로 이동하려는 편향, ...)
4.2-1 DFS
Def) 깊이 우선 탐색(DFS, Depth First Search)
- 현재 정점과 인접한 정점 중 하나를 선택하여 이동하는 과정을 반복.
더이상 이동할 정점이 없을 경우, 뒤쪽으로 백트래킹(Backtracking)하여
다시 이동할 경로를 탐색.
- 시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점을 탐색
- 보통 재귀 또는 스택을 이용하여 구현
Note) 장단점
장점1. 재귀 함수를 활용하여 구현시, 추가적인 공간복잡도가 들어가지 않음.
단점1. 깊이 우선 탐색이기 때문에, 최단 경로가 보장되지 않음.
단점2. 재귀 함수로 구현시 깊이가 너무 깊을 때 스택 오버플로우 발생 가능.
결론. 순환구조를 찾아야 할 때 아주 적합.
Thm) 1차원 DFS 구현 With 재귀함수
<hide/>
#pragma once
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
vector<list<int>> AdjacentList;
vector<bool> VisitVector;
vector<int> DistanceVector;
vector<int> ParentVector;
int V;
void DFS1D(const int CurrentV)
{
VisitVector[CurrentV] = true;
for (int NextV : AdjacentList[CurrentV])
{
if (VisitVector[NextV] == false)
{
cout << CurrentV << " -> " << NextV << endl;
DistanceVector[NextV] = DistanceVector[CurrentV] + 1;
ParentVector[NextV] = CurrentV;
DFS1D(NextV);
}
}
return;
}
void Solve(int n, vector<pair<int, int>>& positions)
{
if (n <= 1)
{
cout << "Not enough vertex to DFS." << endl;
return;
}
V = n;
AdjacentList.assign(V, list<int>());
VisitVector.assign(V, false);
ParentVector.assign(V, -1);
DistanceVector.assign(V, 0);
for (const auto& Position : positions)
{
AdjacentList[Position.first].push_back(Position.second);
AdjacentList[Position.second].push_back(Position.first);
}
DFS1D(0);
return;
}
int main()
{
return 0;
}
Ex) 이색 칠하기
두 개의 색만 존재한다. 인접한 두 정점의 색상은 무조건 다르게 하려고 하는데,
가능한지 불가능한지를 출력하시오.
<hide/>
// TestCase
6
5
0 1
0 2
0 3
0 4
0 5
// Expected
BICOLORABLE
// TestCase
9
10
0 1
0 2
0 3
1 5
2 5
3 4
5 6
5 8
6 7
7 8
// Expected
BICOLORABLE
// TestCase
9 11
0 1
0 2
0 3
1 5
2 5
3 4
4 5
5 6
5 8
6 7
7 8
// Expected
NOT BICOLORABLE<hide/>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
vector<list<int>> AdjacentList;
vector<bool> VisitVector;
vector<int> ColorVector;
int V;
bool DFS1D(const int CurrentV, const int CurrentColor)
{
VisitVector[CurrentV] = true;
ColorVector[CurrentV] = CurrentColor;
for (int NextV : AdjacentList[CurrentV])
{
if (!VisitVector[NextV])
{
// 다음 정점을 다른 색으로 칠하며 탐색
if (!DFS1D(NextV, 1 - CurrentColor))
return false;
}
else if (ColorVector[NextV] == CurrentColor)
{
// 인접한 정점이 같은 색이면 불가능
return false;
}
}
return true;
}
void Solve(int n, vector<pair<int, int>>& positions)
{
if (n <= 1)
{
cout << "BICOLORABLE" << endl;
return;
}
V = n;
AdjacentList.assign(V, list<int>());
VisitVector.assign(V, false);
ColorVector.assign(V, -1);
for (const auto& Position : positions)
{
AdjacentList[Position.first].push_back(Position.second);
AdjacentList[Position.second].push_back(Position.first);
}
// 그래프 탐색 시작
bool IsBicolorable = true;
for (int i = 0; i < V; ++i)
{
if (!VisitVector[i])
{
if (!DFS1D(i, 0))
{
IsBicolorable = false;
break;
}
}
}
if (IsBicolorable)
{
cout << "BICOLORABLE" << endl;
}
else
{
cout << "NOT BICOLORABLE" << endl;
}
return;
}
int main()
{
// TestCase 1
int n1 = 6;
vector<pair<int, int>> positions1 = {
{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}};
cout << "TestCase 1: ";
Solve(n1, positions1);
// TestCase 2
int n2 = 9;
vector<pair<int, int>> positions2 = {
{0, 1}, {0, 2}, {0, 3}, {1, 5}, {2, 5}, {3, 4}, {5, 6}, {5, 8}, {6, 7}, {7, 8}};
cout << "TestCase 2: ";
Solve(n2, positions2);
// TestCase 3
int n3 = 9;
vector<pair<int, int>> positions3 = {
{0, 1}, {0, 2}, {0, 3}, {1, 5}, {2, 5}, {3, 4}, {4, 5}, {5, 6}, {5, 8}, {6, 7}, {7, 8}};
cout << "TestCase 3: ";
Solve(n3, positions3);
return 0;
}
백준1068)
<hide/>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
vector<list<int>> AdjacentList;
vector<bool> VisitVector;
int V;
int LeafCount = 0;
int RootNode, EraseNode;
void DFS1D(const int CurrentV)
{
VisitVector[CurrentV] = true;
bool bIsLeafNode = true;
for (int NextV : AdjacentList[CurrentV])
{
if (VisitVector[NextV] == false && NextV != EraseNode)
{
//cout << CurrentV << " -> " << NextV << endl;
bIsLeafNode = false;
DFS1D(NextV);
}
}
if (bIsLeafNode == true && CurrentV != EraseNode)
{
++LeafCount;
}
return;
}
void Solve(int n, const vector<int>& ParentVector, int eraseNode)
{
if (n <= 1)
{
cout << 0 << endl;
return;
}
V = n;
EraseNode = eraseNode;
AdjacentList.assign(V, list<int>());
VisitVector.assign(V, false);
for (int i = 0; i < V; ++i)
{
if (ParentVector[i] == -1)
{
RootNode = i;
}
else
{
AdjacentList[ParentVector[i]].push_back(i);
}
}
if (RootNode == EraseNode)
{
cout << 0 << endl;
return;
}
DFS1D(RootNode);
cout << LeafCount << endl;
return;
}
int main() {
int n;
cin >> n; // 노드의 개수
vector<int> ParentVector(n);
for (int i = 0; i < n; ++i) {
cin >> ParentVector[i]; // 각 노드의 부모 정보 입력
}
int eraseNode;
cin >> eraseNode; // 지울 노드 입력
Solve(n, ParentVector, eraseNode);
return 0;
}
백준1325)
<hide/>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
vector<list<int>> AdjacentList;
vector<bool> VisitVector;
int V;
vector<int> Memoization;
int DFS1D(const int CurrentV)
{
if (Memoization[CurrentV] != -1)
{
return Memoization[CurrentV];
}
VisitVector[CurrentV] = true;
int HackingCount = 1;
for (int NextV : AdjacentList[CurrentV])
{
if (VisitVector[NextV] == false)
{
HackingCount += DFS1D(NextV);
}
}
VisitVector[CurrentV] = false;
return Memoization[CurrentV] = HackingCount;
}
void Solve(int n, vector<pair<int, int>>& positions)
{
if (n <= 1)
{
cout << 1 << endl;
return;
}
V = n;
AdjacentList.assign(V, list<int>());
Memoization.assign(V, -1); // 메모이제이션 초기화
for (const auto& Position : positions)
{
AdjacentList[Position.second - 1].push_back(Position.first - 1); // 역방향 그래프 생성
}
int MaxHackingCount = 0;
for (int i = 0; i < V; ++i)
{
if (Memoization[i] == -1)
{
VisitVector.assign(V, false);
MaxHackingCount = max(MaxHackingCount, DFS1D(i));
}
}
for (int i = 0; i < V; ++i)
{
if (Memoization[i] == MaxHackingCount)
{
cout << i + 1 << " ";
}
}
cout << endl;
return;
}
int main() {
int n, m;
cin >> n >> m; // 컴퓨터의 개수와 신뢰 관계 수
vector<pair<int, int>> relations(m);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
relations[i] = { a, b }; // a가 b를 신뢰
}
Solve(n, relations);
return 0;
}
백준1992) 쿼드트리
<hide/>
#pragma once
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
string s;
char a[101][101];
string quard(int y, int x, int size) {
if (size == 1) return string(1, a[y][x]);
char b = a[y][x];
string ret = "";
bool flag = 0;
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
if (b != a[i][j]) {
flag = 1;
break;
}
}
if (flag) break;
}
if (!flag) return string(1, b);
ret += '(';
ret += quard(y, x, size / 2);
ret += quard(y, x + size / 2, size / 2);
ret += quard(y + size / 2, x, size / 2);
ret += quard(y + size / 2, x + size / 2, size / 2);
ret += ')';
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < n; j++) {
a[i][j] = s[j];
}
}
cout << quard(0, 0, n) << '\n';
return 0;
}
Thm) 2차원 DFS
<hide/>
#pragma once
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> AdjacentMatrix;
vector<vector<bool>> VisitMatrix;
vector<vector<int>> DistanceMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void DFS2D(const int CurrentVR, const int CurrentVC)
{
VisitMatrix[CurrentVR][CurrentVC] = true;
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && AdjacentMatrix[NextVR][NextVC] != 0)
{
cout << CurrentVR << ", " << CurrentVC << " -> " << NextVR << ", " << NextVC << endl;
DistanceMatrix[NextVR][NextVC] = DistanceMatrix[CurrentVR][CurrentVC] + 1;
DFS2D(NextVR, NextVC);
}
}
return;
}
void Solve(int n, int m, vector<pair<int, int>>& positions)
{
if (n <= 1 && m <= 1)
{
cout << "Not enough vertex to DFS." << endl;
return;
}
VR = m;
VC = n;
AdjacentMatrix.assign(VR, vector<int>(VC, 0));
VisitMatrix.assign(VR, vector<bool>(VC, false));
DistanceMatrix.assign(VR, vector<int>(VC, 0));
for (const auto& Position : positions)
{
AdjacentMatrix[Position.second][Position.first] = 1;
}
for (int i = 0; i < VR; ++i)
{
for (int j = 0; j < VC; ++j)
{
if (VisitMatrix[i][j] == false && AdjacentMatrix[i][j] != 0)
{
DFS2D(i, j);
}
}
}
return;
}
int main()
{
return 0;
}
백준2468)
<hide/>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> AdjacentMatrix;
vector<vector<bool>> VisitMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void DFS2D(const int CurrentVR, const int CurrentVC, const int CurrentHeight)
{
VisitMatrix[CurrentVR][CurrentVC] = true;
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && CurrentHeight < AdjacentMatrix[NextVR][NextVC])
{
DFS2D(NextVR, NextVC, CurrentHeight);
}
}
return;
}
void Solve(int n, const vector<vector<int>>& heights)
{
if (n <= 1)
{
cout << 1 << endl;
return;
}
VR = n;
VC = n;
AdjacentMatrix.assign(VR, vector<int>(VC, 0));
AdjacentMatrix = heights;
int MaxHeight = *max_element(AdjacentMatrix[0].begin(), AdjacentMatrix[0].end());
for (int i = 1; i < VR; ++i)
{
MaxHeight = max(MaxHeight, *max_element(heights[i].begin(), heights[i].end()));
}
int MaxSafeAreas = 0;
for (int CurrentHeight = 0; CurrentHeight <= MaxHeight; ++CurrentHeight)
{
VisitMatrix.assign(VR, vector<bool>(VC, false));
int SafeAreas = 0;
for (int i = 0; i < VR; ++i)
{
for (int j = 0; j < VC; ++j)
{
if (VisitMatrix[i][j] == false && CurrentHeight < AdjacentMatrix[i][j])
{
++SafeAreas;
DFS2D(i, j, CurrentHeight);
}
}
}
MaxSafeAreas = max(MaxSafeAreas, SafeAreas);
}
cout << MaxSafeAreas << endl;
return;
}
int main()
{
int n;
cin >> n;
vector<vector<int>> heights(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> heights[i][j];
}
}
Solve(n, heights);
return 0;
}
백준2583)
<hide/>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> AdjacentMatrix;
vector<vector<bool>> VisitMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int DFS2D(const int CurrentVR, const int CurrentVC)
{
VisitMatrix[CurrentVR][CurrentVC] = true;
int Area = 1;
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && AdjacentMatrix[NextVR][NextVC] == 0)
{
Area += DFS2D(NextVR, NextVC);
}
}
return Area;
}
void Solve(int m, int n, int k, const vector<vector<int>>& rectangles)
{
VR = m;
VC = n;
AdjacentMatrix.assign(VR, vector<int>(VC, 0));
VisitMatrix.assign(VR, vector<bool>(VC, false));
for (const auto& Rectangle : rectangles)
{
int LeftBottomX = Rectangle[0];
int LeftBottomY = Rectangle[1];
int RightTopX = Rectangle[2];
int RightTopY = Rectangle[3];
for (int Y = LeftBottomY; Y < RightTopY; ++Y)
{
for (int X = LeftBottomX; X < RightTopX; ++X)
{
AdjacentMatrix[Y][X] = 1;
}
}
}
vector<int> Areas;
for (int i = 0; i < VR; ++i)
{
for (int j = 0; j < VC; ++j)
{
if (VisitMatrix[i][j] == false && AdjacentMatrix[i][j] == 0)
{
int Area = DFS2D(i, j);
Areas.push_back(Area);
}
}
}
sort(Areas.begin(), Areas.end());
cout << Areas.size() << endl;
for (int Area : Areas) {
cout << Area << " ";
}
cout << endl;
return;
}
int main() {
int m, n, k;
cin >> m >> n >> k; // 모눈종이 크기와 직사각형 개수
vector<vector<int>> rectangles(k, vector<int>(4));
for (int i = 0; i < k; ++i) {
cin >> rectangles[i][0] >> rectangles[i][1] >> rectangles[i][2] >> rectangles[i][3];
}
Solve(m, n, k, rectangles);
return 0;
}
백준2636)
<hide/>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> AdjacentMatrix;
vector<vector<bool>> VisitMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void DFS2D(const int CurrentVR, const int CurrentVC)
{
VisitMatrix[CurrentVR][CurrentVC] = true;
AdjacentMatrix[CurrentVR][CurrentVC] = 2;
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && AdjacentMatrix[NextVR][NextVC] == 0)
{
DFS2D(NextVR, NextVC);
}
}
return;
}
int MeltCheese()
{
int MeltedCheeseCount = 0;
vector<pair<int, int>> MeltingPositions;
for (int i = 0; i < VR; ++i)
{
for (int j = 0; j < VC; ++j)
{
if (AdjacentMatrix[i][j] == 1)
{
int AirCount = 0;
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = i + DirectionMatrix[DirectionIndex][0];
int NextVC = j + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (AdjacentMatrix[NextVR][NextVC] == 2)
{
++AirCount;
}
}
if (0 < AirCount)
{
MeltingPositions.push_back({ i, j });
++MeltedCheeseCount;
}
}
}
}
for (const auto& Position : MeltingPositions)
{
AdjacentMatrix[Position.first][Position.second] = 0;
}
return MeltedCheeseCount;
}
void solve(int n, int m, vector<vector<int>>& cheese)
{
VR = n;
VC = m;
AdjacentMatrix.assign(VR, vector<int>(VC, 0));
AdjacentMatrix = cheese;
int TotalTime = 0;
int LastCheeseCount = 0;
while (true)
{
VisitMatrix.assign(VR, vector<bool>(VC, false));
DFS2D(0, 0);
int CurrentCheeseCount = MeltCheese();
if (CurrentCheeseCount == 0)
{
break;
}
LastCheeseCount = CurrentCheeseCount;
++TotalTime;
}
std::cout << TotalTime << std::endl;
std::cout << LastCheeseCount << std::endl;
return;
}
int main() {
int n, m;
std::cin >> n >> m;
vector<vector<int>> cheese(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cin >> cheese[i][j];
}
}
solve(n, m, cheese);
return 0;
}
4.2-2 BFS
Def) 너비 우선 탐색(BFS, Breadth First Search)
- 현재 정점과 인접한 모든 정점을 방문한 후, 다시 이들 정점과 인접한
모든 정점을 찾아 방문하는 방식.
- 시작 정점으로부터 가까운 정점을 먼저 방문하고,
멀리 떨어진 정점을 나중에 방문.
- 보통 큐를 이용하여 구현
Note) 장단점
장점1. 레벨 순으로 탐색하므로, 간선 가중치가 같을 때 최단 경로를 보장.
장점2. 그래프에서 목표가 여러 개일 경우, 경로를 놓치지 않고 모두 탐색함.
단점1. 큐에 모든 인접 노드를 저장해야 하므로, 인접 노드가 많다면 공간복잡도가 늘어남.
단점2. 모든 레벨을 순차적으로 탐색하므로, 목표 노드가 깊은 곳에 있다면 시간복잡도가 늘어남.
결론. 최단 경로 문제, 전염병 확산 시뮬레이션 같은 레벨 단위 문제, 모든 노드 방문 문제.
Thm) 1차원 BFS 템플릿 코드
<hide/>
#pragma once
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
vector<list<int>> AdjacentList;
vector<bool> VisitVector;
vector<int> DistanceVector;
vector<int> ParentVector;
int V;
void BFS1D(const int StartV)
{
queue<int> AdjacentQueue;
VisitVector[StartV] = true;
AdjacentQueue.push(StartV);
while (AdjacentQueue.empty() == false)
{
int CurrentV = AdjacentQueue.front();
AdjacentQueue.pop();
for (int NextV : AdjacentList[CurrentV])
{
if (VisitVector[NextV] == false)
{
cout << CurrentV << " -> " << NextV << endl;
DistanceVector[NextV] = DistanceVector[CurrentV] + 1;
ParentVector[NextV] = CurrentV;
VisitVector[NextV] = true;
AdjacentQueue.push(NextV);
}
}
}
return;
}
void Solve(int n, vector<pair<int, int>>& positions)
{
if (n <= 1)
{
cout << "Not enough vertex to BFS." << endl;
return;
}
V = n;
AdjacentList.assign(V, list<int>());
VisitVector.assign(V, false);
ParentVector.assign(V, -1);
DistanceVector.assign(V, 0);
for (const auto& Position : positions)
{
AdjacentList[Position.first].push_back(Position.second);
AdjacentList[Position.second].push_back(Position.first);
}
BFS1D(0);
return;
}
int main()
{
return 0;
}
Ex) 아래 입력의 DFS 결과와 BFS 결과를 출력하시오.
<hide/>
// TestCase1
7 9
A B
B E
A E
B C
B F
C F
C D
D G
G F
A
// Expected
ABCDGFE
ABECFDG
Thm) 2차원 BFS 템플릿 코드
<hide/>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define FALSE (0)
#define TRUE (1)
enum { DIR = 4 };
static int sarriDir[DIR][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void BFS(int _iStartVertex, vector<vector<int>> _vviAdjacentMatrix, vector<int> _viVisitMatrix)
{
...
}
void BFS2D(int _iStartRow, int _iStartCol, vector<vector<int>>& _vviAdjacectMatrix, vector<vector<int>>& _vviVisitMatrix)
{
queue<int> qNextRow;
queue<int> qNextCol;
_vviVisitMatrix[_iStartRow][_iStartCol] = TRUE;
qNextRow.push(_iStartRow);
qNextCol.push(_iStartCol);
int iCurrRow, iCurrCol, iVertexCount = _vviVisitMatrix.size();
while (false == qNextRow.empty() && false == qNextCol.empty())
{
iCurrRow = qNextRow.front(); qNextRow.pop();
iCurrCol = qNextCol.front(); qNextCol.pop();
for (int i = 0; i < DIR; ++i)
{
int iNextRow = iCurrRow + sarriDir[i][0];
int iNextCol = iCurrCol + sarriDir[i][1];
if (1 <= iNextRow && iNextRow <= iVertexCount && 1 <= iNextCol && iNextCol <= iVertexCount &&
0 == _vviVisitMatrix[iNextRow][iNextCol] && 1 == _vviAdjacectMatrix[iNextRow][iNextCol])
{
_vviVisitMatrix[iNextRow][iNextCol] = 1;
qNextRow.push(iNextRow);
qNextCol.push(iNextCol);
cout << '(' << iCurrRow << ", " << iCurrCol << ") -> (" << iNextRow << ", " << iNextCol << ')' << endl;
}
}
}
}
int main(void)
{
size_t uVertexCount, uEdgeCount;
cin >> uVertexCount >> uEdgeCount;
vector<vector<int>> vviAdjacentMatrix;
vviAdjacentMatrix.resize(uVertexCount + 1, vector<int>(uVertexCount + 1, 0));
int iVertex1, iVertex2;
for (size_t i = 0; i < uEdgeCount; ++i)
{
cin >> iVertex1 >> iVertex2;
vviAdjacentMatrix[iVertex1][iVertex2] = 1;
}
vector<int> viVisitMatrix;
viVisitMatrix.resize(uVertexCount + 1, 0);
BFS(1, vviAdjacentMatrix, viVisitMatrix);
return 0;
}
Thm) 2차원 BFS 템플릿 코드와 조상노드 및 거리 추가
<hide/>
#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> AdjacentMatrix;
vector<vector<bool>> VisitMatrix;
vector<vector<int>> DistanceMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void BFS2D(const int StartVR, const int StartVC)
{
queue<pair<int, int>> AdjacentQueue;
VisitMatrix[StartVR][StartVC] = true;
pair<int, int> AdjacentQueuePair(StartVR, StartVC);
AdjacentQueue.push(AdjacentQueuePair);
while (AdjacentQueue.empty() == false)
{
int CurrentVR = AdjacentQueue.front().first;
int CurrentVC = AdjacentQueue.front().second;
AdjacentQueue.pop();
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && AdjacentMatrix[NextVR][NextVC] != 0)
{
cout << CurrentVR << ", " << CurrentVC << " -> " << NextVR << ", " << NextVC << endl;
DistanceMatrix[NextVR][NextVC] = DistanceMatrix[CurrentVR][CurrentVC] + 1;
VisitMatrix[NextVR][NextVC] = true;
pair<int, int> NextVPair(NextVR, NextVC);
AdjacentQueue.push(NextVPair);
}
}
}
return;
}
void Solve(int n, int m, vector<pair<int, int>>& positions)
{
if (n <= 1 && m <= 1)
{
cout << "Not enough vertex to BFS." << endl;
return;
}
VR = m;
VC = n;
AdjacentMatrix.assign(VR, vector<int>(VC, 0));
VisitMatrix.assign(VR, vector<bool>(VC, false));
DistanceMatrix.assign(VR, vector<int>(VC, 0));
for (const auto& Position : positions)
{
AdjacentMatrix[Position.second][Position.first] = 1;
}
for (int i = 0; i < VR; ++i)
{
for (int j = 0; j < VC; ++j)
{
if (VisitMatrix[i][j] == false && AdjacentMatrix[i][j] != 0)
{
BFS2D(i, j);
}
}
}
return;
}
int main()
{
return 0;
}
백준1012)
<hide/>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> AdjacentList;
vector<vector<bool>> VisitMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void BFS2D(const int StartVR, const int StartVC)
{
queue<pair<int, int>> AdjacentQueue;
VisitMatrix[StartVR][StartVC] = true;
pair<int, int> AdjacentQueuePair(StartVR, StartVC);
AdjacentQueue.push(AdjacentQueuePair);
while (AdjacentQueue.empty() == false)
{
int CurrentVR = AdjacentQueue.front().first;
int CurrentVC = AdjacentQueue.front().second;
AdjacentQueue.pop();
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && AdjacentList[NextVR][NextVC] != 0)
{
//cout << CurrentVR << ", " << CurrentVC << " -> " << NextVR << ", " << NextVC << endl;
VisitMatrix[NextVR][NextVC] = true;
pair<int, int> NextVPair(NextVR, NextVC);
AdjacentQueue.push(NextVPair);
}
}
}
return;
}
void Solve(int n, int m, vector<pair<int, int>>& positions)
{
if (n <= 1 && m <= 1)
{
cout << "Not enough vertex to BFS." << endl;
return;
}
VR = m;
VC = n;
AdjacentList.assign(VR, vector<int>(VC, 0));
VisitMatrix.assign(VR, vector<bool>(VC, false));
for (const auto& Position : positions)
{
AdjacentList[Position.second][Position.first] = 1;
}
int WormCount = 0;
for (int i = 0; i < VR; ++i)
{
for (int j = 0; j < VC; ++j)
{
if (VisitMatrix[i][j] == false && AdjacentList[i][j] != 0)
{
BFS2D(i, j);
++WormCount;
}
}
}
cout << WormCount << endl;
return;
}
int main() {
int T;
cin >> T;
while (T--) {
int m, n, k;
cin >> m >> n >> k;
vector<pair<int, int>> positions(k);
for (int i = 0; i < k; ++i) {
int x, y;
cin >> x >> y;
positions[i] = { x, y };
}
Solve(m, n, positions);
}
return 0;
}
백준2178)
<hide/>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> AdjacentMatrix;
vector<vector<bool>> VisitMatrix;
vector<vector<int>> DistanceMatrix;
int VR;
int VC;
int DirectionMatrix[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void BFS2D(const int StartVR, const int StartVC)
{
queue<pair<int, int>> AdjacentQueue;
VisitMatrix[StartVR][StartVC] = true;
pair<int, int> AdjacentQueuePair(StartVR, StartVC);
AdjacentQueue.push(AdjacentQueuePair);
while (AdjacentQueue.empty() == false)
{
int CurrentVR = AdjacentQueue.front().first;
int CurrentVC = AdjacentQueue.front().second;
AdjacentQueue.pop();
for (int DirectionIndex = 0; DirectionIndex < 4; ++DirectionIndex)
{
int NextVR = CurrentVR + DirectionMatrix[DirectionIndex][0];
int NextVC = CurrentVC + DirectionMatrix[DirectionIndex][1];
if (NextVR <= -1 || VR <= NextVR ||
NextVC <= -1 || VC <= NextVC)
{
continue;
}
if (VisitMatrix[NextVR][NextVC] == false && AdjacentMatrix[NextVR][NextVC] != 0)
{
DistanceMatrix[NextVR][NextVC] = DistanceMatrix[CurrentVR][CurrentVC] + 1;
VisitMatrix[NextVR][NextVC] = true;
pair<int, int> NextVPair(NextVR, NextVC);
AdjacentQueue.push(NextVPair);
}
}
}
return;
}
void Solve(int n, int m, const vector<vector<int>>& maze)
{
if (n <= 1 && m <= 1)
{
cout << 1 << endl;
return;
}
VR = n;
VC = m;
AdjacentMatrix.assign(VR, vector<int>(VC, 0));
VisitMatrix.assign(VR, vector<bool>(VC, false));
DistanceMatrix.assign(VR, vector<int>(VC, 1));
AdjacentMatrix = maze;
BFS2D(0, 0);
cout << DistanceMatrix[VR - 1][VC - 1] << endl;
return;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> maze(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
string row;
cin >> row;
for (int j = 0; j < m; ++j) {
maze[i][j] = row[j] - '0';
}
}
Solve(n, m, maze);
return 0;
}'C++ > 자료구조와 알고리듬' 카테고리의 다른 글
| 6. Linked list, Hash table (0) | 2022.12.30 |
|---|---|
| 5. Dynamic Programming, Backtracking (0) | 2022.12.01 |
| 3. Tree, Binary Search Tree (0) | 2022.11.04 |
| 2. Sort, Search, Stack, Queue (0) | 2022.10.23 |
| 1. Recursive Function, Array (0) | 2022.10.21 |
댓글