졸지말고..

학습 목표

• BFS 알고리즘의 개념 및 동작 과정을 이해한다.   
• BFS 알고리즘을 구현한다.
• BFS 알고리즘의 시간 복잡도를 분석한다.

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

1. 너비 우선 탐색이란?

 너비 우선 탐색은 깊이 우선 탐색처럼 그래프를 탐색하는 알고리즘입니다. 깊이 우선 탐색과는 다르게 시작 정점에서 가까운 정점부터 탐색해 나가는 방식입니다. 다시 말해, 출발 정점으로부터 탐색을 시작해 먼저 발견된 정점을 탐색한다고 생각하시면 됩니다. 어디서 비슷한 느낌의 자료구조를 보신 적이 있으실 겁니다! 바로 먼저 들어온(First In) 데이터를 먼저 처리(First Out)하는 Queue 입니다. 갑자기 이처럼 Queue를 언급하는 이유는 너비 우선 탐색에서 사용되기 때문입니다. 자세한 내용은 밑에서 설명해드리도록 하고 너비 우선 탐색의 간단한 활용처를 말씀드리겠습니다.

 너비 우선 탐색은 위에서 언급했듯이 출발 정점에서 가까운 정점을 우선적으로 탐색한다는 특징을 갖고 있습니다. 이는 다르게 해석하면 출발 정점으로 가까운 거리에 있는 정점을 탐색한다는 말이며, 어떤 조건에서의 최단 거리 혹은 최솟값을 찾는 데 활용됩니다. 나중에 다룰 최단거리 알고리즘인 다익스트라의 기본이 되기도 합니다. 개인적인 경험을 더해 말씀드리자면, 위에서 언급한 개념 및 특징을 기반으로 여러 기업의 코딩테스트에서 자주 출제되는 개념입니다. 그렇기 때문에 이전 포스팅과는 다르게 글 하단에 너비 우선 탐색을 활용해 해결할 수 있는 알고리즘 문제도 링크를 기재했으니 욕심이 있으신 분들은 한번 해결해보시길 추천드립니다. 이제부터 본격적으로 너비 우선 탐색에 대해서 설명해드리도록 하겠습니다.

2. 알고리즘 동작 과정

1. 출발 정점번호에 대한 방문 정보를 갱신하고, Queue 에 Push한다.
2. Queue 에서 하나의 정점(현재 정점)을 꺼낸다.
3. 현재 정점과 연결된 다른 정점의 방문 정보를 확인한다.
4. 연결된 정점이 이미 방문된 상태라면 무시하고, 그렇지 않다면 방문 정보를 갱신 후 Queue에 Push한다.
5. 2~4 과정을 Queue 에 정점이 들어있지 않을 때 까지 반복한다.

* 여기서 왜 방문표시를 먼저하고, Queue 에 push 하는지 궁금하신 분이 있으실 것 같습니다. 그 이유는 너비 우선 탐색은 먼저 방문한 정점을 먼저 탐색한다고 말씀드렸습니다. 그렇기 때문에 한 정점이 먼저 등장했다는 것은 나중에 발견돼도 이미 방문되어 있을 것이라는 의미입니다. 따라서 이미 발견된 정점을 큐에 push 하는 행위는 무의미한 행위입니다. 오히려 쓸모없는 연산이 발생하는 것입니다. 따라서 확인되는 순간  방문 표시를 하는 것입니다. 아직도 헷갈리신다면, "방문 표시"를 발견 여부를 체크했다고 해석하셔도 좋습니다.

3. 소스코드

- 인접 행렬

#include <iostream>
#include <queue>

using namespace std;

int g[5][5], start; 
bool visited[5];
queue<int> q;
void addEdge(int u, int v){
    g[u][v] = 1;
    g[v][u] = 1;
}
int main(){
    
    //간선 추가
    addEdge(0,1);
    addEdge(2,3);
    addEdge(3,4);
    addEdge(4,1);

    //시작 정점을 큐에 push
    cin >> start;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        //정점 방문
        int now = q.front();
        q.pop();
        cout << now << " 방문\n" ;

        //인접 행렬로 구현하여 간선 유무를 직접 조사한다.
        for(int i = 0; i < 5; i++){
            //now 정점과 i 정점 사이의 간선이 존재하고 i 정점을 방문하지 않았을 때
            if(g[now][i] && !visited[i]){
                //방문 표시 후 큐에 입력
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return 0;
}

- 인접 리스트

#include <iostream>
#include <queue>
#include <list>

using namespace std;

int start; 
bool visited[5];
queue<int> q;
list<int> g[5];
void addEdge(int u, int v){
    g[u].push_front(v);
    g[v].push_front(u);
}
int main(){
    
    //간선 추가
    addEdge(0,1);
    addEdge(2,3);
    addEdge(3,4);
    addEdge(4,1);

    //시작 정점을 큐에 push
    cin >> start;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        //정점 방문
        int now = q.front();
        q.pop();
        cout << now << " 방문\n" ;

        //인접 행렬로 구현하여 간선 유무를 직접 조사한다.
        for(list<int>::iterator iter = g[now].begin(); iter != g[now].end() ; iter++){
            //iter이 가르키는 정점을 방문하지 않았을 때
            if(!visited[*iter]){
                //방문 표시 후 큐에 입력
                visited[*iter] = true;
                q.push(*iter);
            }
        }
    }
    return 0;
}

4. 시간복잡도

 BFS 의 시간복잡도는 그래프 표현 방법에 따라서 달라집니다. 인접 행렬로 그래프를 표현했다면 한 정점에서 다른 정점간의 간선 유무를 파악하기 위해서는 직접 조사를 해야 합니다. 이 과정에서 유효하지 않은 간선(g[u][v]==0)도 조사해야 하기 때문에 인접 행렬의 경우 행렬 크기인 O(V^2)의 시간 복잡도가 소요됩니다. 인접리스트는 인접 행렬과는 다르게 그래프에 유효한 간선만 리스트 형태로 가지고 있습니다. 그렇기 때문에 각 정점을 도는 데 O(V) 만큼의 시간 복잡도와 유효 간선을 파악하는 데 O(E) 만큼의 소요합니다. 따라서 인접리스트는 O(V+E) 만큼의 시간복잡도를 보입니다.

5. 정리

• 시작 정점에서 가까운 정점부터 탐색해 나가는 방식의 그래프 탐색 알고리즘이다.
• 알고리즘의 동작 구조상 Queue 를 사용한다.
• 특정 조건에서의 최단 거리 혹은 최솟값을 찾는 데 활용된다.
• 인접 행렬로 구현하면 O(V^2) 의 시간복잡도를 갖고, 인접리스트로 구현하면O(E+V)의 시간복잡도를 갖는다. 

6. 관련 문제

★☆☆ 단지 번호 붙이기 https://www.acmicpc.net/problem/2667

★★☆ 불 https://www.acmicpc.net/problem/5427 

★★★ 통나무 옮기기 https://www.acmicpc.net/problem/1938

학습 목표

• DFS 알고리즘이 무엇인지 이해한다.

• DFS 알고리즘의 동작 과정을 이해한다.

• DFS 알고리즘을 소스코드로 구현한다.

깊이 우선 탐색(DFS, Depth-First Search) 알고리즘이란?

 그래프 탐색 알고리즘입니다. 그래프 탐색 알고리즘은 그래프 내 모든 정점을 방문하는 방법입니다. DFS는 이름에서 알 수 있듯이 깊이를 우선시하는 탐색 알고리즘입니다. 다시 말해, 한 정점에서 연결된 간선을 살펴보면서 방문 가능한 정점이 있다면, 즉시 방문하는 방식으로 동작하는 알고리즘입니다. 

 위에서 언급했듯이 방문 가능한 정점이 있으면 바로 방문합니다. 이 동작 방식은 재귀 호출을 사용하여 구현하면 간단하게 구현됩니다. 정점을 방문하는 과정을 함수 호출, 더 이상 방문할 정점이 없을 경우 이전 정점으로 돌아오는 과정을 함수 리턴으로 생각해 구현합니다.

탐색 과정

알고리즘의 동작 과정은 다음 세 단계로 이루어집니다.

1. 탐색 시작 정점을 방문합니다.

2. 현재 정점(또는 시작 정점)에서 연결된 간선을 순차적으로 탐색합니다.

• 탐색 중인 정점이 방문한 정점이라면, 다음 정점을 확인합니다.

• 탐색 중인 정점이 방문하지 않은 정점이라면 이 정점을 방문하여 2번 과정을 진행합니다.(재귀 호출)

3. 더 이상 방문할 정점이 없다면 탐색을 끝냅니다.(함수 리턴)

소스 코드(인접 행렬)

시간 복잡도

 시간 복잡도 분석을 위해 두 가지 그래프 형태를 고려하겠습니다. 우선, 주어진 그래프가 인접 리스트일 경우에는 모든 정점을 확인하는 복잡도인 |V|, 각 정점에서 연결된 간선들을 확인하는 과정에서 |E| 만큼 소요됩니다. 따라서 인접 리스트 형태의 그래프를 DFS 방식으로 탐색할 경우 O(|V|+|E|) 만큼의 시간 복잡도를 보입니다.

 그래프가 인접 행렬 형태로 주어진다면 각 정점에서 연결된 간선들을 확인하는데 |V| 만큼 시간 복잡도가 필요합니다. 따라서 인접 행렬 형태의 그래프를 DFS 방식으로 탐색할 경우 O(|V|^2) 만큼의 시간 복잡도를 보입니다.

정리

• 그래프 상의 모든 정점을 깊이 우선 방식으로 탐색하는 알고리즘이다.

• 방문 가능한 정점이 있다면 즉시 방문하는 방식으로 동작한다.

• 동작 원리를 고려해 재귀 함수로 구현하면 간단하다.

• 시간 복잡도는 인접 리스트로 구현 시 O(|V|+|E|), 인접 행렬로 구현 시 O(|V|^2)이다.

1. 문제를 꼼꼼히 읽자

몇번을 강조해도 부족할만큼 중요하다고 생각합니다. 여러 유형의 문제를 풀면서도 이부분을 간과하고, 대충 접근하면 잘못된 코드로 수정에만 대부분의 시간을 소모했던 경험이 많았습니다. S기업 SW관련 행사에 갔을 때도 담당자 분이 몇번을 강조하시더라구요! 다시 한번 말씀드리겠습니다. 문제를 제대로 읽는 것이 풀이 시간 단축의 지름길입니다. 

2. 입출력의 사이즈를 확인하자

여기서 말하는 사이즈는 입력에 대한 N크기의 사이즈가 아닙니다. 입출력 변수의 자료형 범위를 말하는 것 입니다. 오늘도 문제를 풀다가 출력사이즈가 int 자료형을 넘어가는 부분을 고려하지 못했습니다. 그래서 멀쩡한 코드만 몇번을 리뷰하는 삽질을 했는데.. 만약 코딩테스트였다면 아찔합니다.. 인생의 나락으로... OTL 어쨌든! 다시 말하자면, 입출력 변수의 자료형이 주어지는 입력과 예상되는 출력의 범위를 포함할 수 있는지 보는 게 중요합니다! 이것 또한 헛된 시간 낭비를 방지하는 방법 중 하나이기 때문이죠. 

3. 시간복잡도를 생각하자

알고리즘 문제를 풀때, 풀이가 바로 떠올라도 한 번 의심할 필요가 있습니다. 물론 아주 쉬운 문제를 풀때는 그 풀이가 맞겠지만, 어느 정도의 난이도가 있는 문제를 풀때는 그 방법이 정답이 아닐 수가 있습니다. 그렇기 때문에 대략 실행시간 1초를 1~2억번의 명령 라인 실행으로 생각하고, 본인이 적용하려는 알고리즘의 시간복잡도와 일치하는지 보는 게 중요합니다. 그러면 잘못된 알고리즘을 적용하는 실수를 줄일 수 있으닌깐요!

알고리즘 문제를 풀면서 중요하다고 느꼈던 부분들을 수시로 업데이트 하겠습니다.