(백준 4803번 트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 2 with gpt

오늘은 gpt 선생님에게 한 수 배웠다.

 

백준 4803번

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

 

 

일단 gpt가 풀어준 풀이는 아래와 같다. 

§ dfs(int node, int parent)를 정의해줘서 부모가 아닌데 방문된 노드를 만나면 순환이 있다고 판단

§ 처음 시작은 dfs(node, -1)로 시작

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
vector<vector<int>> graph;
vector<bool> visited;

// DFS 함수, 순환이 있는지 체크
bool dfs(int node, int parent) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            if (!dfs(next, node)) return false;
        } else if (next != parent) {
            // 부모가 아닌데 방문된 노드를 만나면 순환 존재
            return false;
        }
    }
    return true;
}

int countTrees() {
    int treeCount = 0;
    visited.assign(n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            // 각 연결 요소가 트리인지 검사
            if (dfs(i, -1)) {
                treeCount++;
            }
        }
    }
    return treeCount;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int caseNumber = 0;
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        graph.assign(n + 1, vector<int>());
        
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        int result = countTrees();
        cout << "Case " << ++caseNumber << ": ";
        if (result == 0) {
            cout << "No trees.\n";
        } else if (result == 1) {
            cout << "There is one tree.\n";
        } else {
            cout << "A forest of " << result << " trees.\n";
        }
    }
    return 0;
}

 

이걸 익히고 내가 푼 풀이.. 순환이 있는지를 확인하는게 어려웠다.

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

class Tree {
public:
	int N;
	vector<vector<int>> adj;
	vector<bool> visited;

	Tree(int N) : N(N) {
		adj.resize(N + 1);
		visited.resize(N + 1, false);
	}

	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void findTree(){
		int ans = 0;
		// ★ for(int i = 0; i < N; i++)이 아님!!!
		for (int i = 1; i < N+1; i++) {
			if (visited[i] == false) {
				//cout << "dfs(i, -1) " << dfs(i, -1) << endl;
				if (dfs(i, -1)) {
					ans++;
				}
			}
		}

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

	bool dfs(int curr, int parent) {
		visited[curr] = true;
		//if (!adj[curr].empty()) {
			for (int next : adj[curr]) {
				if (visited[next] == false) {
					// ★ dfs(next, curr)의 결과에 따라 return하는 값이 다름
					if(!dfs(next, curr)) return false;
				}
				//★ curr!= parent가 아님!!
				else if (next != parent) {
					return false;
				}
			}
		//}
		return true;
	}
};

int main() {
	int n, m; int nCase = 1;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) break;
		Tree t(n);
		for (int i = 0; i < m; i++) {
			int u, v; cin >> u >> v;
			t.addEdge(u, v);
		}

		cout << "Case " << nCase++ << ": ";
		t.findTree();
	}
}

 

gpt보다 잘하고 싶은데, 그건ㅋㅋㅋㅋ너무 어려운 일 같다ㅎㅎ

그래도 이 코드를 나름 이해한 것만으로도 만-족

 

클래스를 만들어서 그런가 시간이 무려 4배나 차이난다..ㄷ

 

그리고 이 문제를 Union Find로도 풀 수 있는 것 같다!

Union Find 풀이는 다음에 도전!