[백준 4803 C++][G4] 트리

⭐️ 난이도

Gold 4

---

⭐️ 문제

https://www.acmicpc.net/problem/4803

4803번: 트리

 

---

⭐️ Idea flow

 

문제에서 "트리는 사이클이 없는 연결 요소"라는 조건을 주었다.

input에서 정점과 간선의 개수를 입력받고, 간선에 대한 정보(간선이 잇는 두 노드의 숫자)가 주어진다.

이를 통해 양방향 간선을 추가하여 그래프를 형성할 수 있다.

 

이후 BFS/DFS를 통해 간선을 타고 탐색한다.

탐색을 하던 도중 이미 방문한 노드에 도달하게 된다면 해당 연결 요소에는 사이클이 형성된다.

위와 같은 방법으로 사이클이 형성되는지의 유무를 알 수있다.

 

사이클이 형성 되었다면, 해당 탐색에서는 트리가 없다는 뜻이고

사이클이 형성되지 않았다면, 해당 탐색에서 트리가 있다는 뜻이다.

 

바깥 함수에서는 모든 노드를 검사하면서 만일 방문하지 않은 노드일 때 BFS/DFS를 실행하고,

사이클이 형성되지 않은 경우에 tree의 개수를 늘려준다.

 

마지막으로 tree의 개수에 따라서 적절한 문구를 출력한다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 4803 - 트리
vector<vector<int>> graph;
vector<int> isVisited;

void input(int& n, int& m){
    graph.assign(n + 1, vector<int>(0, 0));
    isVisited.assign(n + 1, false);

    for(int i = 0; i < m; i++){
        int s = 0, e = 0;
        cin >> s >> e;
        graph[s].emplace_back(e);
        graph[e].emplace_back(s);
    }
}

bool DFS(int idx, int before){
    isVisited[idx] = true;

    for(int i = 0; i < graph[idx].size(); i++){
        int next = graph[idx][i];
        if(next == before)  continue; // 바로 이전에 방문한 곳인 경우 pass

        if(isVisited[next]) return false;
        if(!DFS(next, idx)) return false;
    }
    return true;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int idx = 0;
    while(true){
        int n, m, tree = 0;
        cin >> n >> m;
        if(n == 0 && m == 0)    break;

        input(n, m);
        idx++;

        for(int i = 1; i <= n; i++){
            if(!isVisited[i]){
                if(DFS(i, 0))   tree++;
            }
        }

        if(tree == 0)   cout << "Case " << idx << ": No trees.\n";
        else if(tree == 1)  cout << "Case " << idx << ": There is one tree.\n";
        else    cout << "Case " << idx << ": A forest of " << tree <<" trees.\n";
    }

    return 0;
}

 

---

⭐️ Feedback

 

전체적인 알고리즘의 플로우는 금방 떠올랐지만 DFS로 구현하는 과정에서 살짝 난항이 있었다.

양방향 그래프이고, 간선을 검사할 때에 연결된 모든 간선을 검사한다.

때문에 바로 이전에 타고 온 간선을 검사했을 때 방문한 노드로 가게 되므로 거기서 사이클이 생겼다고 체크하고 검사가 끝나버렸다.

 

이렇게 되면 제대로 된 검사가 되지 않는다.

따라서 바로 이전에 방문했던 노드의 번호를 변수 before에 저장해 둔 다음,

만일 이번에 검사하는 간선에 이어져있는 노드가 before이라면 continue를 통해 다음 간선을 검사하도록 한다.