[백준] 4803번 : 트리

문제

 

---

풀이

 

트리의 가장 큰 특징은 사이클이 없단 것이다.

이러면 안된다는 뜻이다.

 

그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다.

근데 dfs를 많이 사용해봤다면 이런 생각이 들 수 있다.

dfs는 가능한 정점을 찾을 때 visited를 체크하는데 그럼 2가 이미 visited 였을테니 4->2가 될리 없지 않나?

그래서 연결된 정점을 찾고 dfs를 실행할 때는 visited를 체크하지 않는다.

 

근데 이러면 또 이런 생각이 들 수 있다.

그럼 1->2를 가고도 2->1이 탐색 가능해지는거고 이럼 무한루프가 되는거 아닐까?

그렇기 때문에 dfs의 현재 정점과 더불어 이 정점이 어떤 정점에서 이어져온 것인지 직전 정점도 저장한다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
int tree_cnt;
bool isTree;

void dfs(int cur, int source) {
    if (visited[cur]) { //사이클 형성
        isTree = false;
        return;
    }
    visited[cur] = true;
    for (int i = 0; i < graph[cur].size(); i++) { //단방향 탐색
        if (graph[cur][i] != source) //1->2로 탐색했었다면 2->1은 탐색하지 않도록
            dfs(graph[cur][i], cur);
    }
}

void printResult(int num, int cnt) { //출력
    cout << "Case " << num;
    switch (cnt) {
        case 0:
            cout << ": No trees.\n";
            break;
        case 1:
            cout << ": There is one tree.\n";
            break;
        default:
            cout << ": A forest of " << cnt << " trees.\n";
    }
}

int main() {
    int a, b, c, d, tc = 0;

    while (true) {
        tc++;
        cin >> a >> b;
        if ((a == 0) && (b == 0))
            break;
        graph.assign(a + 1, vector<int>(0));
        visited.assign(a + 1, false);
        for (int i = 0; i < b; i++) {
            cin >> c >> d;
            graph[c].push_back(d);
            graph[d].push_back(c);
        }

        tree_cnt = 0;
        for (int i = 1; i <= a; i++) {
            if (!visited[i]) {
                isTree = true;
                dfs(i, -1);
                if (isTree) //사이클이 없었으면 트리임임
                    tree_cnt++;
            }
        }
        printResult(tc, tree_cnt);
    }
}

전체 소스코드다.

 

        tree_cnt = 0;
        for (int i = 1; i <= a; i++) {
            if (!visited[i]) {
                isTree = true;
                dfs(i, -1);
                if (isTree) //사이클이 없었으면 트리임임
                   tree_cnt++;
            }
        }
        printResult(tc, tree_cnt);

각 테스트케이스의 모든 정점에 대해 dfs를 실행한다.

dfs를 실행하고 isTree가 true라면 사이클 없이 잘 빠져나왔단 뜻이니 tree_cnt를 늘려준다.

모든 정점을 탐색하면 printResult 함수로 결과를 출력한다.

 

void dfs(int cur, int source) {
    if (visited[cur]) { //사이클 형성
        isTree = false;
        return;
    }
    visited[cur] = true;
    for (int i = 0; i < graph[cur].size(); i++) { //단방향 탐색
        if (graph[cur][i] != source) //1->2로 탐색했었다면 2->1은 탐색하지 않도록
            dfs(graph[cur][i], cur);
    }
}

이 dfs에서는 visited 여부를 이번에 선택된 정점에 대해 검사한다.

이번 정점이 이전에 탐색했던 정점이라면 사이클이 형성된 것이다.

 

무사히 빠져나왔다면 탐색 가능한 정점들을 탐색하고 dfs를 호출한다.

 

void printResult(int num, int cnt) { //출력
    cout << "Case " << num;
    switch (cnt) {
        case 0:
            cout << ": No trees.\n";
            break;
        case 1:
            cout << ": There is one tree.\n";
            break;
        default:
            cout << ": A forest of " << cnt << " trees.\n";
    }
}

이건 그냥 출력함수다.