[BOJ 백준] 트리인가?(6416) C++

 

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

6416번: 트리인가?

 

문제 설명 : 

트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. 이때, 노드 u에서 노드 v로 가는 간선이 존재하면 간선을 u에 대해서는 '나가는 간선', v에 대해서는 '들어오는 간선'이라고 하자.

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

아래의 그림을 보자. 원은 노드, 화살표는 간선을 의미하며, 화살표의 방향이 노드 u에서 노드 v로 향하는 경우 이는 이 간선이 u에서 나가는 간선이며 v로 들어오는 간선이다. 3개의 그림 중 앞의 2개는 트리지만 뒤의 1개는 트리가 아니다.

당신은 간선의 정보들을 받아서 해당 케이스가 트리인지를 판별해야 한다.

 

입력 : 

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 입력의 끝에는 두 개의 음의 정수가 주어진다.

각 테스트 케이스는 여러 개의 정수쌍으로 이루어져 있으며, 테스트 케이스의 끝에는 두 개의 0이 주어진다.

각 정수쌍 u, v에 대해서 이는 노드 u에서 노드 v로 가는 간선이 존재함을 의미한다. u와 v는 0보다 크다.

출력 : 

각 테스트 케이스에 대해서, 테스트 케이스의 번호가 k일 때(k는 1부터 시작하며, 1씩 증가한다) 트리일 경우 "Case k is a tree."를, 트리가 아닐 경우 "Case k is not a tree."를 출력한다.

 

예제 입력 : 

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1

예제 출력 : 

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.

 

 

접근법 : 

1) 어떻게 풀 것인가?

구현 문제

indegree, outdegree 활용 고민

리프 노드에서부터 거슬러 가면서 삭제 / root만 남기는 함수를 통해 root 1개인지, 단일경로인지 확인

루트 노드부터 bfs로 뿌리는 방식도 괜찮을듯

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 트리인가? 6416 C++ 
#if 1
#pragma warning(disable:4996)
#include <iostream>
#include <set>
#include <vector>
#include <queue>

#define MAX (10000+3)

using namespace std;

typedef pair<int, int> pii;

vector<int> indegree[MAX];
int outdegree[MAX];
set<int> tree;  // 중복허용하지 않음

int edgeCnt;

bool isTree;

void init();
int removeLeaf();
void output(int tc);

int main() {

	//freopen("input.txt", "r", stdin);

	int input1, input2;
	isTree = false;
	edgeCnt = 0;
	for (int tc = 1; ; ) {
		scanf("%d %d", &input1, &input2);
		// 탈출조건
		if (input1 == -1 && input2 == -1) break;

		// tree 종료 ==> 검증 필요
		if (input1 == 0 && input2 == 0) {

			// 가능한 경우, flag를 true로 변경
			int leafCnt = removeLeaf();
			if (tree.size() == 0 || tree.size() == leafCnt + 1) {
				isTree= true;
			}

			// 출력하기
			output(tc);

			// 초기화
			init();
			tc++;	// 테스트 케이스 증가
			
		}

		else {
			indegree[input2].push_back(input1);
			if (input1 != input2) {
				outdegree[input1]++;
			}
			tree.insert(input1);
			tree.insert(input2);
		}

	}
	return 0;
}

void init() {
	tree.clear();
	for (int i = 0; i < MAX; i++) {
		outdegree[i] = 0;
		indegree[i].clear();
	}
	isTree = false;
	edgeCnt = 0;
}

int removeLeaf() {
	queue<int> que;
	int result = 0;

	// 자식들 Queue에 넣고 쭉 제거 해보자
	for (auto cur : tree) {
		if (indegree[cur].size()== 1 && outdegree[cur] == 0 ) {
			que.push(cur);
		}
	}

	while (!que.empty()) {
		result++;
		int id = que.front(); que.pop();

		if (indegree[id].size() == 1) {
			vector<int> connected;
			for (auto next : indegree[id]) {
				connected.push_back(next);
			}
			for (auto next : connected) {
				outdegree[next]--;
				if (indegree[next].size() == 1 && outdegree[next] == 0) {
					que.push(next);
				}
			}
		}
	}
	return result;
}

void output(int tc) {
	if (isTree) {
		printf("Case %d is a tree.\n", tc);
	}
	// 2) 트리가 아니면
	else {
		printf("Case %d is not a tree.\n", tc);
	}
}
#endif