백준 - 31476 :blob_twintail_thinking:

문제

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

31476번: :blob_twintail_thinking:

트리를 레벨 순회, 중위순회 하는 문제였다.

 

• 양갈래 블롭
  • 같은 레벨은 가장 오래 걸린 시간이 소요된다.
  • 이때, 분기할 때마다 소요 시간이 T만큼 증가한다 (U+T, U+2*T, U+3*T...)
• 포니테일 블롭
  • 중위순회 하면서 갔다가 돌아오는 길에도 탐색 시간이 U만큼 소요된다.

 

문제 풀이

트리 그래프를 먼저 만들어줬다. 완전이진트리여서 단순하게 현재 노드의 좌, 우, 즉 0,1번째 노드를 추가했고 이를 마지막 번호가 나올때까지 반복했다.

 

연결을 끊는 것은 end에서부터 start까지 parent를 이용해 거슬러 올라가면서 연결을 끊었다. 해당 노드가 짝수일 경우에는 왼쪽 노드, 홀수일 경우에는 오른쪽 노드로  간주했고 부모 노드의 해당 방향과 연결된 노드를 -1로 만들었다.

 

포니테일 순회는 중위순회를 돌며 방문할 때와 돌아올 때 U를 더해줬다. 이때, 마지막 노드에서 1까지 거슬러 올라가는 길은 탐색하지 않아도 되는데 더해지는 것이기 때문에 나중에 빼줬다.

 

트윈테일 순회는 레벨 별 순회를 돌면서 각 레벨마다 가장 많이 걸린 시간을 더해줬다.

해당 레벨에서 분기가 한 번이라도 있다면 분기 카운트를 늘렸다. 그리고 queue에서 현재 레벨과 이전 레벨이 달라질 때 해당 레벨의 시간인 (U+T*분기 count)를 더해줬다.

 

int D, N, U, T;
vector<vector<int>> G;
vector<int> parent;
int lastNum;
int ponyCnt, twinCnt;
int ponyLast=1;

void printParent() {
	for (int i = 1; i < lastNum; i++) {
		printf("%d ", parent[i]);
	}
	printf("\n------------------\n");
}

void makeTree() {
	queue<int> q;
	q.push(1);

	int n = 2;
	parent[1] = 1;
	while (n<lastNum) {
		int nowNum = q.front();
		q.pop();

		G[nowNum].push_back(n);
		G[nowNum].push_back(n+1);
		parent[n] = nowNum;
		parent[n + 1] = nowNum;
		
		q.push(n);
		q.push(n + 1);

		n += 2;
	}
}

void makeDisconnect(int s, int e) {

	int n = e;
	while (true) {		

		if (n % 2 == 0)
			G[parent[n]][0] = -1;
		else G[parent[n]][1] = -1;

		n = parent[n];
		
		if (n == s)
			break;
	}
}

void ponySearch(int n) {
	ponyLast = n;

	if(G[n].size()>0) {
		if (G[n][0] != -1) {
			ponyCnt += U;
			ponySearch(G[n][0]);
		}

		if (G[n][1] != -1) {
			ponyCnt += U;
			ponySearch(G[n][1]);
		}
	}

	
	ponyCnt += U;
}

void twinSearch(int start) {
	queue<pair<int,int>> q; //node, level
	q.push({ start,0});

	int beforeLevel = 0;
	bool isSeperate = false;
	int seperateCnt = 0;
	while (!q.empty()) {
		int n = q.front().first;
		int nowLevel = q.front().second;
		q.pop();

		if (beforeLevel != nowLevel) {			
			if (isSeperate) seperateCnt++;
			twinCnt += (U + T * seperateCnt);			
			beforeLevel = nowLevel;			
			isSeperate = false;
		}
		
		int cnt = 0;
		for (int i = 0; i < G[n].size(); i++) {			
			int nextNode = G[n][i];
			if (nextNode != -1) {
				q.push({ nextNode,nowLevel + 1 });
				cnt++;
			}
		}
		if (cnt == 2) {		
			isSeperate = true;
		}
	}
}

int calDoubleSum(int n) {
	int result = 0;

	while (true) {
		if (n == 1) break;
		result += U;
		n = parent[n];
	}

	//1도 두번 체크됨
	result += U;

	return result;
}

int main() {

	scanf("%d %d %d %d", &D, &N, &U, &T);
	lastNum = pow(2, D);
	G = vector<vector<int>>(lastNum, vector<int>());
	parent = vector<int>(lastNum, false);

	makeTree();
	//printParent();

	//끊어진 구간
	for (int i = 0; i < N; i++) {
		int s, e;
		scanf("%d %d", &s, &e);
		makeDisconnect(s, e);
	}
	ponyCnt = 0;
	twinCnt = 0;

	//포니테일 순회
	ponySearch(1);

	ponyCnt -= calDoubleSum(ponyLast);

	twinSearch(1);

	if (ponyCnt > twinCnt)
		printf(":blob_twintail_aww:");
	else if (ponyCnt < twinCnt)
		printf(":blob_twintail_sad:");
	else
		printf(":blob_twintail_thinking:");
	return 0;
}

/*
4 3 1 4
2 5
3 7
3 6
*/