[알고리즘] 그래프,DFS, BFS, 백트래킹

kodaaa·2022년 7월 4일
BFSDFS그래프백트래킹알고리즘코테준비
0

코딩테스트

목록 보기
4/17
post-thumbnail

그래프

📢 그래프

  • 정점 : Node, Vertex
  • 간선 : Edge
  • 차수 : degree
    • 무방향그래프 : 노드에 연결된 간선 수
    • 방향그래프 : indegree(노드로 들어오는 간선 수), outdegree(노드에서 뻗어나가는 간선 수)

📢 그래프 종류

  • 사이클
    • 어떤 정점에서 다시 그 정점으로 돌아올 수 있는 경로
  • 완전 그래프
    • 서로 다른 두 정점이 하나의 간선으로 연결되는 그래프
  • 연결 그래프
    • 모든 정점이 연결되어 있음
    • 어떤 정점에서 다른 모든 정점으로 갈 수 있는 길이 있음
  • 비연결 그래프
    • 연결되어 있지 않은 정점이 존재
  • 루프
    • 어떤 정점에서 자기 자신으로 가는 간선
  • 한 정점에서 다른 정점으로 가는 간선이 여러 개 있을 수 있다

📢 그래프 구현

🔎 1. 인접 행렬

무방향 그래프

  • 정점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개인 그래프일 때,

  • 어떤 정점 i, j가 연결되어있는지 확인 : O(1)
    • 그냥 adj[i][j]값에 바로 접근
  • 어떤 정점 i에 연결된 다른 정점들 확인 : O(V)
    • adj[i][1]~adj[i][V] 값(총 V개)을 모두 확인해야 하니까
  • 필요한 메모리 : O(V^2)
    • 정점 수가 10만개만 돼도 40GB가 나오기 때문에 거의 대부분 메모리초과 나올 것



🔎 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개인 그래프일 때,

  • 어떤 정점 i, j가 연결되어있는지 확인 : O(i의차수+j의차수)
    • adj[i] 벡터, adj[j] 벡터의 원소들 모두 확인해야 하니까
  • 어떤 정점 i에 연결된 다른 정점들 확인 : O(i의차수)
    • adj[i] 벡터의 원소들을 확인
    • 그래프를 이용할 때 이 연산을 많이 이용하기 때문에 인접행렬에 비해 시간 복잡도가 적은건 아주 장점임
  • 필요한 메모리 : O(V+E)
    • 정점 개수만큼의 배열 크기(V) + E(최대2*E지만 빅오표기법에서는 상수는 무시)
    • 아주 좋다!

👉 메모리, 시간복잡도의 이점 때문에 주로 인접리스트를 사용


그래프 탐색

  • 그래프의 모든 정점을 1번씩만 방문

    • 💡 N*M 사이즈 2차원 배열 내에서 뭔가를 찾는거면 일단 그래프(BFS, DFS, 백트래킹) 생각하자
    • 주로 격자판이 나오는 문제

  • 시간복잡도 : 인접행렬의 경우 O(V^2), 인접리스트의 경우 O(V+E) 로 BFS, DFS 모두 동일

📢 BFS

BFS(Breadth First Search) : 너비 우선 탐색


🔎 구현 : 큐를 이용

  • visited 배열
    • 각 정점이 이미 방문한 정점인지 아닌지 표시
    • 값은 true / false
  • 큐
    • 방문할 정점들
    • 큐에서 하나 꺼낸 정점이 현재 방문하는 정점
    • 이 정점과 연결된 모든 정점들 중 아직 방문하지 않은 정점들을 큐에 새로 넣음
      • 방문한 정점인지 아닌지 확인할 때 visited 배열 조회
      • 큐에 넣은 직후 visited배열에 방문한 정점이라고 표시
      • 큐에 들어간 정점들은 모두 visited배열값이 true
    • 큐의 pop 연산을 할 땐 항상 while(!q.empty()){ } 문 안에서 수행
      • 큐가 비지 않았을 때만 pop을 수행하도록. 안그러면 오류남
#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

  • level을 통해 최단거리를 구할 수 있음
    • 목적지의 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;
      }
    }
  }
}

💡 언제 쓸까?

  • 그냥 그래프를 탐색(모든 정점을 한번씩 방문)하고 싶을 때
  • 모든 간선의 가중치가 같을 경우
    • 최단 경로(정점a에서 정점b까지의 최단경로) 구할 때
      • == 정점a를 시작점으로 할 때, 정점 b가 몇 level에 있는지
      • 가중치가 다를 경우 최단경로 구하는 알고리즘은 따로 있음
        • 다익스트라
    • 시작점으로부터 같은 거리 상에 있는 점들을 묶어야 할 때
      • == 시작점으로부터 같은 level에 있는 점들

🔎 연결 요소(Connected Component)

연결된 노드들(어떤 노드에서 다른 모든 노드로 가는 길이 존재) 덩어리




📢 DFS

DFS(Depth First Search) : 깊이 우선 탐색

한 루트로 탐색하다가 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식


🔎 구현 : 스택/재귀함수를 이용

1. 스택을 이용한 구현

큐를 이용한 BFS 구현과 완전히 비슷! 큐 대신 스택을 사용한다는 것 빼고 코드상 차이는 없음.

  • visited 배열
    • 각 정점이 이미 방문한 정점인지 아닌지 표시
    • 값은 true / false
  • 스택
    • 방문할 정점들
    • 스택에서 하나 꺼낸 정점이 현재 방문하는 정점
    • 이 정점과 연결된 모든 정점들 중 아직 방문하지 않은 정점들을 큐에 새로 넣음
      • 방문한 정점인지 아닌지 확인할 때 visited 배열 조회
      • 스택에 넣은 직후 visited배열에 방문한 정점이라고 표시
      • 스택에 들어간 정점들은 모두 visited배열값이 true
    • 스택의 pop 연산을 할 땐 항상 while(!q.empty()){ } 문 안에서 수행
      • 스택이 비지 않았을 때만 pop을 수행하도록. 안그러면 오류남
#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;
      }
    }
  }
}

2. 재귀함수를 이용한 구현

DFS는 스택을 이용해 구현하는 경우는 거의 없고, 대부분 재귀함수를 이용함.

📌 재귀함수

  • 자기 자신을 다시 호출하는 방법으로 문제를 해결하는 함수

    • if 조건으로 재귀 호출 멈춰야 함

  • 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의 일반화

노드의 서브트리에 대해 각각 DFS를 수행하는 것과 같음.

  • 노드 n을 시작점으로 DFS를 하는 것은, 노드 n의 서브트리들(노드 a를 루트로 하는 트리, 노드 b를 루트로 하는 트리..)에서 각각 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;
}

📌 트리의 지름

  • 트리

    • 사이클이 없고, 간선이 양방향(undirected)인 그래프

  • 트리의 지름

    • 트리에서 가장 멀리 떨어져 있는 두 정점 간 거리

  • DFS/BFS로 트리의 지름 구하기

    1. 트리에서 아무 한점이나 선택
    2. 그 점에서 가장 멀리 떨어진 점 u를 찾기(DFS 혹은 BFS를 통해)
    3. u에서 가장 멀리 떨어진 점 v를 찾기(DFS 혹은 BFS를 통해)
    4. u와 v간 거리가 트리의 지름!

    👉 시작 정점을 어떤걸로 잡아도 그 정점과 가장 먼 정점은 트리의 양 끝점 중 하나임

  • 예시

    시작 정점을 어떤 걸로 잡아도 그 정점과 가장 먼 정점(2나 9)은 트리의 양 끝점 중 하나




📢 백트래킹

DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는다.

💡 언제 쓸까?

  • 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 사용한다.
    - N*M에서 n개의 장애물을 세우는 모든 경우의 수를 다 실행해봐야 하는 경우에는 백트래킹 이용!

💡 포인트

  • DFS, BFS, 최선우선탐색으로 구현 가능하지만, 경우의 수 구하기는 DFS가 제일 낫다.

💡 연습문제

  • 9663 N-Queen

  • 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';
   }
 }

  • 1991 트리 순회

  • 14502 연구소 : 벽 세우기-백트래킹, 바이러스 번짐-BFS

    • N*M에서 n개의 장애물을 세우는 모든 경우의 수를 다 실행해봐야 하는 경우에는 백트래킹 이용!

    • outOfBound 주의

      • N*M 내에서 상하좌우 이동해야 할 때는 배열 크기를 [N+2][M+2]로 해두면 outOfBound 위험이 없다
        • 실제 사용 범위는 1~N, 1~M
        • 실제 사용 범위가 아닌 원소의 값은 해당 배열에서 있을 수 없는 값으로 채움
        • 상하좌우 이동시 배열 이용하면 편함
        int dx[4] = {0, 0, -1, +1};
 int dy[4] = {-1, +1, 0, 0};
      • if문에서 0<=x && 0<=y && x<N && y<M && 다른 기타 조건... 으로 두어도 outOfBound 위험이 없다. 대신 저 범위 조건을 arr[x][y]에 접근하는 코드보다 앞에 써야 함!
        • if문에서 &&나 ||연산자가 있을 때, 왼쪽부터 차례로 실행. 조건에 안맞으면 다음 연산 실행하지 않고 바로 끝냄
    • 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
알고리즘 소모임 알림 자료

profile
kodaaa
취뽀하자(●'◡'●)💕
이전 포스트

[알고리즘] 그리디 알고리즘

다음 포스트

[자료구조] 우선순위 큐, 큐

0개의 댓글