Study note/Coding test

그래프 탐색 알고리즘: DFS/BFS

공대 아로마 2024. 4. 12. 17:25

기술면접을 위해 기초 CS에 대한 복습중이다.
공부한 내용 중 요점이나 나중에 기억해야할 부분을 정리해보려고 한다.
내가 아는 부분은 생략되어 있을 수 있고, 혹여나 틀린 부분이 있을 수도 있으니 이 글을 보고 '다른 사람'이 공부하기에는 도움이 되지 않을 수 있으니 주의!

Stack in C++

stack<int> s;    // 선언

s.push(5);        // 5를 push
s.top();        // 최상단 원소
s.pop();        // 5를 pop

Queue in C++

queue<int> q;    // 선언

q.push(5);        // 5를 push
q.front();        // 가장 먼저 들어온 원소
q.pop();        // 5를 pop

재귀함수 (Recursive)

  • stack처럼 가장 나중에 호출된 recursive 함수가 가장 먼저 종료된다.
  • 팩토리얼 구하는 게 가장 대표적인 recursive 함수다.
  • GCD(최대공약수) 구하는 것도 재귀함수다.
  • 점화식으로 구할 때 주로 이용된다.

DFS (Depth-First Search)

  • Stack(혹은 recursive)을 이용해서 깊이 우선으로 탐색
  • 방문처리 표시할 bool 배열과 그래프 리스트들의 배열이 필요하다.
  • bool visited[9]; vector<int> graph[9];
  • 기본 알고리즘(Stack)
    1. 탐색 시작 노드를 stack에 push하고 visit 처리한다.
    2. stack 최상단 노드에 방문하지 않은 노드가 있으면 그 노드를 push하고, 없다면 pop한다.
    3. 더이상 2번을 할 수 없을 때까지 반복한다.
  • 기본 알고리즘(Recursive)
    1. 현재 노드 x를 visit 처리한다.
    2. 현재 노드에 연결된 다른 노드, graph[x]를 재귀적으로 방문한다.
void dfs(int x) {
    // 현재 노드를 방문 처리
    visited[x] = true;
    cout << x << ' ';
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) dfs(y);
    }
}

BFS (Breadth-First Search)

  • 기본 알고리즘
    1. 탐색 시작 노드를 q.push()하고 visit 처리한다.
    2. q.pop()을 하고, 방금 q.front에 해당했던 노드의 인접 노드 중 방문하지 않은 노드를 모두 push하고, visit 처리한다.
    3. 더이상 2번을 할 수 없을 때까지 반복한다.
void bfs(int start) {
    queue<int> q;
    q.push(start);
    // 현재 노드를 방문 처리
    visited[start] = true;
    // 큐가 빌 때까지 반복
    while(!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for(int i = 0; i < graph[x].size(); i++) {
                int y = graph[x][i];
                if(!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

문제해결 아이디어

  • 연결된 그래프 관련 문제는 DFS나 BFS로 풀면 된다.
  • DFS는 모든 경로를 방문해야 할 경우에 적합하다.
    • 경로의 특징을 저장해야 할 때 (BFS는 경로의 특징이 없음)
    • 검색 대상 그래프가 정말 클 때
  • BFS는 최소비용이 중요할 때 적합하다.
    • 미로 찾기, 최단 거리 구할 때
    • 검색 대상 규모가 크지 않을 때

참고한 사이트

'Study note > Coding test' 카테고리의 다른 글

DP - Dynamic Programming  (0) 2024.04.12
Binary Search  (0) 2024.04.12
그리디 & 구현  (0) 2024.04.12
코딩 테스트에서 주의할 점  (1) 2024.04.12
정렬 알고리즘(Sort)  (0) 2024.04.12