[알고리즘] DFS, BFS (깊이우선탐색, 너비우선탐색) + 백준1260번

그래프

그래프 G = (V, E)

이때 V는 노드, E는 에지이다. 에지 E는 V * V 의 부분집합이다 (즉 노드와 노드를 연결하는 모든 쌍의 부분집합)

유향그래프 vs 무향그래프 : 에지의 방향성에 따라

• 유향그래프 : (i, j) ≠ (j, i)
• 무향그래프 : (i, j) = (j, i)  양방향 유향그래프

가중그래프 G = (V, E, W)

• 가중그래프(weighted graph)는 에지마다 가중치 W를 가진다

보통 사람은 그래프를 손으로 그려 시각적으로 보는 걸 선호하지만, 컴퓨터로는 2차원 행렬 또는 리스트로 표현한다.

그래프의 탐색 자체는 그리 어렵지 않다. 효율적인 탐색을 위해 깊이우선, 너비우선 탐색으로 분류할 수 있다. 그리 어렵지 않은 내용이므로 그림은 과감히 생략ㅎ

깊이우선탐색 (Depth First Search)

깊이우선탐색은 연결된 노드를 따라 계속해 탐색하는 것으로, 더 이상 탐색할 노드가 없을 때까지 이어진 에지를 타고 깊게 들어간다. DFS는 최대한 한붓그리기로 붓이 끊어지지 않을 때까지 탐색한다.

• 시간복잡도 : 탐색 여부를 알아야 하므로 어쨌거나 모든 노드와 에지를 조사해야 한다 O(|V| + |E|)
• 공간복잡도 : 모든 노드에 방문 여부를 체크해야 하므로 O(|V|)

너비우선탐색 (Breadth First Search)

너비우선탐색은 한 노드에서 연결된 노드를 계속 탐색하는 것이다. DFS가 노드 하나하나를 깊이있게 파는거라면, BFS는 넓고 얕게 탐색한다. 이때 어떤 특정 노드에 연결된 노드를 차례대로 확인해야 하므로 FIFO(First In, First Out)의 큐(Queue)를 사용한다. 

• 시간복잡도 : 모든 노드가 큐에 들어갔다 나와야 하고, 이는 연결된 에지를 모두 확인하는 과정이므로 O(|V| + |E|)
  
• 공간복잡도 : 모든 노드에 방문 여부를 확인하고, 큐에 들어가 있는지를 체크해야 하므로 O(|V|)

🧨 그래프 탐색 알고리즘, DFS와 BFS의 구현

• 문제 출처 : 백준 1260번
• 문제 난이도 : 실버2
• 문제 링크 : www.acmicpc.net/problem/1260

1260번: DFS와 BFS

가중치가 없는 무향 그래프에서의 DFS, BFS를 구현했다. 역시나 교수님 코드를  참고해 작성했다. 

깊이우선탐색은 재귀적으로 호출해 깊게 들어갈 수 있도록 했고, 너비우선탐색은 Queue를 이용해 같은 레벨의 노드를 차례대로 방문하도록 했다. 교수님은 그래프를 리스트로 구현하셨지만 C++로 옮기는 과정에서 탐탁치 않아 행렬로 바꿨다.

+ 백준 1260번은 아마 리스트로 구현하면 시간초과가 날 가능성이 높아서 2차원 행렬로 했다.

+ push_back 이나 기타 동적할당이 필요한 게 아니라면 int [] 배열을 쓰자.

+ 재작년 알고리즘 수업 들을 때 교수님이 왜 isinQueue가 또 하나 더 필요한건지 설명해주셨는데 까먹었다. 작년 수업을 들은 파릇파릇한 친구들의 기억을 믿어보겠다 ^^

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, v;
int isMarked[1001] = {false};

void recursiveDFS(int G[1001][1001], int start) {
    if (isMarked[start]) return;
    else {
        isMarked[start] = true;
        cout << start << ' ';
        // no weight DFS (가중치 없는 노드와 연결된 노드만 입력받는 DFS)
        for (int i = 1; i < n + 1; i++) {
            if (G[start][i] && isMarked[i] == false)
                recursiveDFS(G, i);
        }
        return;
    }
}

void BFS(int G[1001][1001], int start) {
    int isMarked[1001] = {false};
    int isinQueue[1001] = {false};
    
    queue<int> q;
    q.push(start);
    isinQueue[start] = true;
    
    while(!q.empty()) {
        int current = q.front();
        q.pop(); //void
        cout << current << ' ';
        isMarked[current] = true;
        
        for(int i = 1; i < n + 1; i++) {
            if(!isMarked[i] && !isinQueue[i] && G[current][i]) {
                q.push(i);
                isinQueue[i] = true;
            }
        }
    }
    return;
}

int main() {
    cin >> n >> m >> v;
    int G[1001][1001] = {0};
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        G[x][y] = 1;
        G[y][x] = 1;
    }

    recursiveDFS(G, v);
    cout << '\n';
    BFS(G, v);

    return 0;
}