그래프
정점a와 정점b가 연결되어 있으면 adj[a][b]=1
, adj[b][a]=1
정점a와 정점b가 연결되어 있지 않으면 adj[a][b]=0
, adj[b][a]=0
예시
정점1과 정점3이 연결된 상태 : 1행 3열, 3행 1열의 값을 1
구현
정점 수, 간선 수, 각 간선이 잇는 정점들을 입력으로 받음
int adj[VMAX+1][VMAX+1]; //C++에서 전역변수로 배열 선언하면 자동으로 0으로 초기화해줌
int v,e; //정점, 간선
cin >> v >> e;
for(int i=0; i<e; i++){
int x, y;
cin >> x >> y;
adj[x][y]=1; //x->y 간선 존재
adj[y][x]=1; //y->x 간선 존재
}
정점a->정점b 간선이 있으면 있으면 adj[a][b]=1
정점a->정점b 간선이 없으면 adj[a][b]=0
구현
정점 수, 간선 수, 각 간선이 잇는 정점들을 입력으로 받음
int adj[VMAX+1][VMAX+1]; //C++에서 전역변수로 배열 선언하면 자동으로 0으로 초기화해줌
int v,e; //정점, 간선
cin >> v >> e;
for(int i=0; i<e; i++){
int x, y;
cin >> x >> y;
adj[x][y]=1; //x->y 간선 존재
}
정점 V개, 간선 E개인 그래프일 때,
O(1)
adj[i][j]
값에 바로 접근O(V)
adj[i][1]
~adj[i][V]
값(총 V개)을 모두 확인해야 하니까O(V^2)
구현
vector<int> adj[MAXV+1]; //혹은 이차원 벡터도 가능
int main()
{
int v, e;
cin >> v >> e;
for(int i=0; i<e; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y); //x->y
adj[y].push_back(x); //y->x
}
}
구현
vector<int> adj[MAXV+1]; //혹은 이차원 벡터도 가능
int main()
{
int v, e;
cin >> v >> e;
for(int i=0; i<e; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y); //x->y
}
}
정점 V개, 간선 E개인 그래프일 때,
O(i의차수+j의차수)
adj[i]
벡터, adj[j]
벡터의 원소들 모두 확인해야 하니까O(i의차수)
O(V+E)
그래프 탐색
그래프의 모든 정점을 1번씩만 방문
시간복잡도 : 인접행렬의 경우 O(V^2)
, 인접리스트의 경우 O(V+E)
로 BFS, DFS 모두 동일
BFS(Breadth First Search) : 너비 우선 탐색
#include <iostream>
#include <vector>
#include <queue>
const int MAXV = 7; //정점 개수
vector<int> adj[MAXV+1]; //인접리스트
bool visited[MAX+1] = {false}; //visited 배열
void bfs(int start) //start는 시작정점
{
queue<int> q;
q.push(start);
visited[start] = true;
while(!q.empty()){
int now = q.front(); //큐는 front, 스택은 top
q.pop();
for(const auto &e : adj[now]){
if(!visited[e]){
q.push(e);
visited[e] = true;
}
}
/*
for(int i=0; i<adj[now].size(); i++){
int e = adj[now][i];
if(!visited[e]){
q.push(e);
visited[e] = true;
}
}
*/
}
}
목적지의 level = 출발지~목적지의 최단거리
주황색 : 정점을 0개 거친 후 방문할 수 있음 - level 0
파란색 : 정점을 1개 거친 후 방문할 수 있음 - level 1
초록색 : 정점을 2개 거친 후 방문할 수 있음 - level 2
같은 레벨 안에서의 정점 방문 순서는 상관 없으나, 레벨의 구성원과 레벨간 순서는 바뀌지 않음
level 배열을 두어서 각 정점의 level을 저장
현재 정점에 인접한 정점의 level = 현재 정점의 level + 1
#include <iostream>
#include <vector>
#include <queue>
const int MAXV = 7; //정점 개수
vector<int> adj[MAXV+1]; //인접리스트
bool visited[MAX+1] = {false}; //visited 배열
int level[MAX+1] = {0}; //level 배열
void bfs(int start) //start는 시작정점
{
queue<int> q;
q.push(start);
visited[start] = true;
while(!q.empty()){
int now = q.front(); //큐는 front, 스택은 top
q.pop();
for(const auto &element : adj[now]){
if(visited[element] == false){
q.push(element);
visited[element] = true;
level[element] = level[now] + 1;
}
}
}
}
연결된 노드들(어떤 노드에서 다른 모든 노드로 가는 길이 존재) 덩어리
DFS(Depth First Search) : 깊이 우선 탐색
한 루트로 탐색하다가 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식
큐를 이용한 BFS 구현과 완전히 비슷! 큐 대신 스택을 사용한다는 것 빼고 코드상 차이는 없음.
#include <iostream>
#include <vector>
#include <stack>
const int MAXV = 7; //정점 개수
vector<int> adj[MAXV+1]; //인접리스트
bool visited[MAX+1]; //visited 배열
void dfs(int start)
{
stack<int> s;
s.push(start);
visited[start] = true;
while(!s.empty()){
int now = s.top();
s.pop();
for(const auto &element : adj[now]){
if(visited[element] == false){
s.push(element);
visited[element] = true;
}
}
}
}
DFS는 스택을 이용해 구현하는 경우는 거의 없고, 대부분 재귀함수를 이용함.
자기 자신을 다시 호출하는 방법으로 문제를 해결하는 함수
ex) 피보나치 함수 : f(n) = f(n-1) + f(n-2)
ex2) 팩토리얼도 재귀로 표현 가능 : n! = n * (n-1)!
int Factorial(int n)
{
if(n==0)
return 1;
else return n*Factorial(n-1);
}
노드의 서브트리에 대해 각각 DFS를 수행하는 것과 같음.
void dfs(int start)
{
if(visited[start]==true) return;
visited[start] = true;
for(int next : adj[start]){
if(!visited[next]){
dfs(next);
}
}
}
👉 BFS와 달리 DFS는 한 정점에서 다른 정점까지의 최단거리 구하기에 이용할 수 없다!
방향그래프에서 사이클은, Back edge(자신의 조상 정점과 연결되어있는 간선) 이 있을 때 생김.
같은 정점이 함수호출스택에서 다시 등장하면 back edge를 찾을 수 있음.
3, 7, 12가 서로 사이클을 이루고 있다는 걸 알 수 있음
사이클을 탐지하는 DFS 구현
vector<vector<int>> graph;
vector<bool> visited;
vector<bool> isInStack; //함수호출스택에 들어있는 함수(정점)인지
bool dfs(int start) //이 그래프에 사이클이 있는지없는지를 반환
{
if(isInStack[start]) return true; //스택에 있는 정점
if(visited[start]) return false; //이미 방문한 정점
visited[start] = true;
isInStack[start] = true;
for(int next : graph[start]){
if(dfs(next)) return true; //연결된 정점에 대해 dfs를 했는데 사이클을 발견한다면 true반환
}
isInStack[start] = false;
return false;
}
트리
트리의 지름
DFS/BFS로 트리의 지름 구하기
- 트리에서 아무 한점이나 선택
- 그 점에서 가장 멀리 떨어진 점 u를 찾기(DFS 혹은 BFS를 통해)
- u에서 가장 멀리 떨어진 점 v를 찾기(DFS 혹은 BFS를 통해)
- u와 v간 거리가 트리의 지름!
👉 시작 정점을 어떤걸로 잡아도 그 정점과 가장 먼 정점은 트리의 양 끝점 중 하나임
예시
시작 정점을 어떤 걸로 잡아도 그 정점과 가장 먼 정점(2나 9)은 트리의 양 끝점 중 하나
DFS
를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는다.
DFS
, BFS
, 최선우선탐색
으로 구현 가능하지만, 경우의 수 구하기는 DFS
가 제일 낫다.18428 감시피하기 : 장애물 두기-백트래킹
void dfs(int idx, int cnt)
{
cout << "!";
if (cnt == 3) //장애물 다 세운 후 실행할 동작 - 선생님 시야 확인
{
for (int i = 0; i < teacher.size(); i++)
{
if (!check(teacher[i].first, teacher[i].second))
{
return;
}
}
cout << "YES";
exit(0);
}
for (int i = idx; i < blank.size(); i++)
{
arr[blank[i].first][blank[i].second] = 'O';
dfs(i + 1, cnt + 1);
arr[blank[i].first][blank[i].second] = 'X';
}
}
14502 연구소 : 벽 세우기-백트래킹, 바이러스 번짐-BFS
N*M에서 n개의 장애물을 세우는 모든 경우의 수를 다 실행해봐야 하는 경우에는 백트래킹 이용!
outOfBound 주의
int dx[4] = {0, 0, -1, +1};
int dy[4] = {-1, +1, 0, 0};
0<=x && 0<=y && x<N && y<M && 다른 기타 조건...
으로 두어도 outOfBound 위험이 없다. 대신 저 범위 조건을 arr[x][y]에 접근하는 코드보다 앞에 써야 함!void dfs(int idx, int cnt)
{
if (cnt == 3)
{
//벽을 다 세웠을 때 실행할 동작 - 바이러스 전파
return;
}
for (int i = idx; i < blank.size(); i++
{
arr[blank[i].first][blank[i].second] = 1;
dfs(i + 1, cnt + 1);
arr[blank[i].first][blank[i].second] = 0;
}
}
참고자료
https://fomaios.tistory.com/entry/Algorithm-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking%EC%9D%B4%EB%9E%80
알고리즘 소모임 알림 자료