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

📌문제 설명

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

 

💡생각

바킹독의 트리 강의 문제집에 들어있는 문제였다.

그래서 트리로 풀어야겠다고 문제에 접근을 했었다. -> 강의를 들을때는 괜찮지만 혼자서 다른 문제를 풀때는 알고리즘을 생각해내면서 공부하는게 더 도움이 되는거 같다!!

 

문제 해결

• 각각의 입력을 받아서 인접한지 여부를 확인해서 저장한다.
• 그리고 각 노드의 부모노드가 무엇인지 확인을 해준다. 그리고 방문했다는 표시를 해준다(visited)
• 부모가 아닌데 이미 방문한 노드를 다시 만나게 된다면 사이클이 발생한 것이다. -> 사이클 발생 이걸 생각하는게 오래 걸렸다.
• 모든 정점이 연결된게 아닐 수 있어서 visited를 통해서 정점중 연결된 구간을 전부 검색해준다.
• 트리에서는 정점 하나만 있어도 트리로 간주한다.

🔥풀이

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

#define CASE1 "Case %d: A forest of %d trees."
#define CASE2 "Case %d: There is one tree."
#define CASE3 "Case %d: No trees."


bool is_tree(vector<vector<int> >& adj, vector<bool> & visited,vector<int> & parent, int root){
    queue<int> q;
    q.push(root);
    visited[root] = true;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int next : adj[cur]){
            if (!visited[next]) {
                visited[next] = true;
                parent[next] = cur;
                q.push(next);
            } else if (parent[cur] != next) { //부모가 아닌데 이미 방문한 노드를 다시 만남
                return false;
            }
        }
    }
    return true;
}

int main(){
    int n = 0, m = 0;
    int edge1, edge2;
    int test_num = 1;
    while(true){
        int T = 0; // 트리의 갯수
        cin >> n >> m;
        vector<bool> visited(n + 1, false);
        vector<int>  parent (n + 1, 0);
        vector<vector<int> > adj(n + 1);
        if(n == 0 && m == 0){
            break;
        }
        for(int i = 0; i <= n; i++){
            visited[i] = false;
            parent[i] = 0;
        }
        for(int i = 0; i < m; i++){
            cin >> edge1 >> edge2;
            adj[edge1].push_back(edge2);
            adj[edge2].push_back(edge1);
        }

        for(int i = 1; i <= n; i++){
            if(!visited[i] && is_tree(adj,visited,parent,i)) {
                T++;
            }
        }
        if(T == 0){
            printf(CASE3"\n", test_num);
        }
        else if(T == 1) {
            printf(CASE2"\n", test_num);
        }
        else{
            printf(CASE1"\n", test_num, T);
        }
        test_num++;
    }
}

 

혼자 문제를 풀때는 알고리즘을 생각하는게 가장 어려운거 같은데 강의를 보고 연습문제를 푸니까 해당 알고리즘을 이용해서 구현하면 된다고 생각해서 상대적으로 쉽게 느껴지는 거 같다. 하지만 알고리즘 구상부터 구현까지 한번에 하는게 중요하기 때문에 개념을 습득하고 랜덤으로 여러 문제를 많이 풀어봐야 할거 같다!!😀