백준 6416번 트리인가?

문제링크: https://www.acmicpc.net/problem/6416

사용한 알고리즘: DFS(?)


트리인지 아닌지 판단하는 문제였습니다. 트리는 root 가 하나여야 하고, root를 제외한 나머지 모든 node 들의 indegree ( 해당 node 로 들어오는 edge 의 개수 ) 가 1 이어야합니다.

문제 풀이는 다음과 같습니다.
(1) node 들이 1,2,3,4, ... 등으로 순서대로 들어오는 게 아니기 때문에 tree를 구성하는 노드들이 입력되면 이를 set으로 저장합니다.

(2) 각 입력 a, b 를 받으면서 벡터 배열로 a 의 자식이 b가 있음을 저장하고, 다른 int 배열을 만들어 b의 indegree++ 을 해줍니다.

(3) 우선 set으로 모은 모든 점들의 indegree들을 보면서 indegree 가 0 인 점, 즉 root 가 단 한개 인지, 다른 모든 점들의 indegree 는 모두 1 인지 확인해줍니다.

(4) 과정 (3)에서 구한 root 를 시작으로 DFS 를 돌려줍니다. DFS 를 돌릴때는 root를 시작으로 모든 자식들을 다시 DFS 함수로 넣어주는 식으로 진행됩니다. 이때 방문하게 되는 자식들을 체크해주어, root에서 시작하여 모든 점들을 단 1회 방문하는지 확인해줍니다.

과정 (4)가 필요한 이유를 반례를 들어 설명드리면,
root 가 1이고 1->2, 1->3 인 점 3개로 구성된 tree 하나와, 서로 edge가 있는 두점 4,5, 즉 4->5, 5->4 인 두 점이 입력으로 주어지면, 과정 (1)~(3)으로는 이 경우가 tree가 맞다고 판단하게 됩니다. 따라서 root에서 각 점을 1회 방문하는지 확인해 주어야 합니다.

	#include <bits/stdc++.h>
	using namespace std;
	int a, b, cnt, root, indegree[100001], Way[100001];
	set<int> Num;
	vector<int> tree[100001];
	bool flag;
	// root 부터 모든 점으로 단 한번만 갈 수 있는지 체크
	void Findway(int R){
	for (int child: tree[R]){
	// 이미 한번 갈 수 있는 점이나, root 자기 자신으로 가는 길이 있으면 틀린거.
	if(child==root||Way[child]==1){
	flag = false;
	return;
	}
	// 해당 점을 가는 방법이 있음을 Way[child]=1로 저장.
	Way[child]=1;
	Findway(child);
	}
	}
	void IsItTree(){
	for(auto iter: Num){
	// root 제외 다른 점들은 indegree 가 1 이어야 해요!
	if(indegree[iter]>1){
	flag = false;
	return;
	}
	// indegree가 0 이면 root 입니다.
	else if(indegree[iter]==0) {
	if(root==-1)root=iter;
	// root 는 유일하게 존재해야 되요. 이미 root 가 있으면 틀린거.
	else{
	flag=false;
	return;
	}
	}
	}
	// root가 없어도 안되죠.
	if(root==-1){
	flag=false;
	return;
	}
	Findway(root);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while(1){
	cnt++;
	root = -1;
	for(auto iter: Num) tree[iter].clear();
	Num.clear();
	memset(indegree,0,sizeof(indegree));
	memset(Way,0,sizeof(Way));
	flag = true;
	cin >> a >> b;
	if(a<0&&b<0) break;
	// 시작부터 0 0 들어오면 tree 라고 말해주어야 합니다.... 이거 찾느라 오래걸렸어요...ㅠㅠ
	else if(a==0&&b==0) cout<<"Case " << cnt << " is a tree."<<'\n';
	else{
	Num.insert(a);
	Num.insert(b);
	tree[a].push_back(b);
	indegree[b]++;
	while(1){
	cin >> a >> b;
	if(a==0&&b==0){
	cout<<"Case "<< cnt;
	IsItTree();
	for(auto iter: Num){
	if(iter==root) continue;
	if(Way[iter]!=1) flag=false;
	}
	if(flag) cout << " is a tree." << '\n';
	else cout << " is not a tree." << '\n';
	break;
	}
	else{
	Num.insert(a);
	Num.insert(b);
	tree[a].push_back(b);
	indegree[b]++;
	}
	}
	}
	}
	return 0;
	}

view raw BOJ 6416.cpp hosted with ❤ by GitHub