백준 6416 트리인가? 문제 C++ unorderd_set 사용 풀이

12 May 2019

Reading time ~3 minutes

이번 문제는 백준 6416 트리인가? 문제입니다.

풀이

이번꺼는 정말 기나긴 여정이었습니다..

핵심적인 데이터 부분위주로 설명드릴께요

 vector<vector<int>> getqu(MAX);

이것은 부모노드의 자식노드를 저장하는 백터입니다.

추가는

 getqu[pushOne].push_back(getOne);

이런식으로 저장합니다.

ex) 1 2 1 3 1 4 이런식으로 데이터가 들어온다면

getqu[1] - 2, 3 , 4 이런식으로 1의 자식노드는 2, 3, 4 다 ! 라는 용도로 사용 됩니다.

그다음은

  vector<int> findRoot(MAX, 0);

이 백터에는 루트를 찾기 위하여 사용되며 또한, 부모가 둘 이상인 노드를 잡아 내기 위하여 사용됩니다.

1 ) 부모가 둘 이상인 노드 잡기

  if (findRoot[getOne] != 0) {
	  ok = 0;
	}

2 ) 루트 찾기 - for문으로 findRoot 중에 0 인것을 찾으시면 됩니다.

그 다음은

  unordered_set<int> list;

입니다.

unordered_set 이란 해시 를 사용합니다.

이걸 이용하여서, 각 노드들의 리스트를 확인도 하고, 모든 노드들을 방문 했는지 확인도 할 것입니다.

unorderd_set 은 find, erase, 등 거의 모든 기능을 해시이기때문에 O(1) 에 수행을 해줍니다.

알아둔다면 언젠간 유용하게 쓰일 태니 꼭 따로 찾아서 알아보시는걸 추천합니다.

마지막으로

 queue<int> search;

가 바로 탐색 노드입니다.

자세한건 아래 전체 코드에 주석으로 첨부합니다.

# 전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#define MAX 30000

using namespace std;


int main() {

	int getOne;
	int pushOne;
	int ok;
	int end = 1;
	int n = 1;
	int zend;
	while (end) {
		zend = 1;
		ok = 1;
		pushOne = 1;
		getOne = 1;

		vector<vector<int>> getqu(MAX);
		vector<int> findRoot(MAX, 0);
		unordered_set<int> list;
		queue<int> search;
		int root = 0;
		while (true) {
			// 입력 
			cin >> pushOne >> getOne;
			if (pushOne <= 0 && getOne <= 0)
				break;
			auto iter = list.find(pushOne);
			// list 에 있으면 넣지말고, 없으면 넣는다. 
			if (iter == list.end())
				list.insert(pushOne);
			iter = list.find(getOne);
			if (iter == list.end())
				list.insert(getOne);
			getqu[pushOne].push_back(getOne);
			// 부모노드 2개 이상일시 감지
			if (findRoot[getOne] != 0) {
				ok = 0;
			}
			// 부모노드 = 자식노드 일시 감지( ex 1 1 )
			if (pushOne == getOne)
				ok = 0;
			findRoot[getOne] = pushOne;
		}
		// 종료 조건 ( 둘다 음수)
		if (getOne < 0 && pushOne < 0) {
			end = 0;
			break;
		}

		// 하나의 노드표를 다 받았을때 ( 0, 0 받았을때). 노드 갯수가 0개인 것도 노드임으로
		// list.empty 도 확인을 해줘야한다.
		if (getOne == pushOne && getOne == 0 && ok != 0 &&!list.empty()) {
			for (auto iter = list.begin(); iter != list.end(); iter++) {
				// 루트도느 찾기. 부모노드가 없으면 루트노드.
				if (findRoot[*iter] == 0) {
					// 만약 루트 노드가 2개 이상이면 트리아님
					if (root != 0) {
						ok = 0;
						break;
					}
					root = *iter;
				}
			}
			// 루트노드가 없으면 트리아님.
			if (root == 0)
				ok = 0;
			else {
				// 부모노드로부터 출발해서 모든 노드를 다 탐색 할수 있는지 확인.
				// 발견한 것은 list에서 지워나감. 
				// 최종적으로 list가 모두 지워지면 정상적인 트리이다.
				list.erase(root);
				while (list.size()) {
					for (int i = 0; i < getqu[root].size(); i++) {
						search.push(getqu[root][i]);
						list.erase(getqu[root][i]);
					}
					root = search.front();
					search.pop();
					if (search.empty() && getqu[root].empty() && !list.empty()) {
						ok = 0;
						break;
					}
				}

			}
		}


		if (ok == 0) {
			cout << "Case " << n << " is not a tree.\n";
		}
		else
			cout << "Case " << n << " is a tree.\n";
		n++;
	}
	return 0;
}