Softeer-연습문제-[21년 재직자 대회 예선] 로드 밸런서 트래픽 예측(C++)

Sechan Oh 2023. 5. 30. 12:02

문제 링크 :

https://softeer.ai/practice/info.do?idx=1&eid=629

문제 개요 :

시간초과 코드 (브루트포스)

#include<iostream>
#include<vector>

using namespace std;

void req(unsigned long node, vector<vector<unsigned long>> tree,
vector<unsigned long> &pointer, vector<unsigned long> &answer);

int main(int argc, char** argv)
{
	unsigned long N, K;
	scanf("%lu %lu", &N, &K);

	vector<unsigned long> answer(N, 0);
	vector<unsigned long> pointer(N, 1);
	vector<vector<unsigned long>> tree; // len, data

	for (int i=0; i<N; i++){
		unsigned long n;
		scanf("%lu", &n);
		vector<unsigned long> tmp;
		for(int j=0; j<n; j++){
			unsigned long n2;
			scanf("%lu", &n2);
			tmp.push_back(--n2);
		}
		tree.push_back(tmp);
		tree[i].insert(tree[i].begin(), n+1);
	}

	for(unsigned long i=0; i<K; i++){
		req(0, tree, pointer, answer);
	}

	for(int i=0; i<N; i++){
		printf("%lu ", answer[i]);
	}

	return 0;
}

void req(unsigned long node, vector<vector<unsigned long>> tree,
vector<unsigned long> &pointer, vector<unsigned long> &answer){
	// ans++, ptr++, 재귀
	answer[node]++;
	if (tree[node][0]==1) return; // leaf
	unsigned long nxt_node = tree[node][pointer[node]];
	req(nxt_node, tree, pointer, answer);
	if (tree[node][0]==++pointer[node]) pointer[node]=1;
}

시간초과 코드(batch 처리)

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main(int argc, char** argv)
{
	// N, K 입력받기
	unsigned long N, K;
	scanf("%lu %lu", &N, &K);

	vector<unsigned long> answer(N, 0);
	vector<unsigned long> tmp_req(N, 0);
	vector<unsigned long> pointer(N, 0);
	vector<vector<unsigned long>> tree;
	queue<unsigned long> q;

	// data 입력받기
	for (unsigned long i=0; i<N; i++){
		unsigned long n;
		scanf("%lu", &n);
		vector<unsigned long> tmp;
		for(int j=0; j<n; j++){
			unsigned long n2;
			scanf("%lu", &n2);
            // tree에 넣을 자식노드
			tmp.push_back(--n2);
		}
		tree.push_back(tmp);
	}

	// 초기값 설정
	tmp_req[0] = K;
	q.push(0);

	// main
	while (q.empty()==false){
		// 다음노드 호출
		unsigned long node = q.front();
		q.pop();
		// 노드의 크기 가져오기
		unsigned long n_sz = tree[node].size();
		// 이 노드의 tmp_req 값이 있고 leaf 노드가 아닐 경우
		if (tmp_req[node]>0 && n_sz>0){
			// 노드의 req값 가져오기
			unsigned long req = tmp_req[node];
			// 최대 point 구하기
			unsigned long max_point = pointer[node] + req % n_sz;
			// 사이클 수 구하기
			unsigned long cycle = req/n_sz;
			// 사이클이 있을 경우
			if (cycle>0){
				// 자식 노드를 돌면서
				for (unsigned long i=0;i<n_sz;i++){
					// 자식노드 찾기
					unsigned long child = tree[node][i];
					// 자식노드의 tmp_req 추가
					tmp_req[child] += cycle;
					// 자식노드를 queue에 추가
					q.push(child);
				}
				// pointer 움직이면서
				for (unsigned long i=pointer[node];i<max_point;i++){
					// 자식노드 찾기
					unsigned long child = tree[node][i%n_sz];
					// 자식노드의 tmp_req 증가
					tmp_req[child]++;
				}
			}
			else{
				// pointer 움직이면서
				for (unsigned long i=pointer[node];i<max_point;i++){
					// 자식노드 찾기
					unsigned long child = tree[node][i%n_sz];
					// 자식노드의 tmp_req 증가
					tmp_req[child]++;
					// 자식노드를 queue에 추가
					q.push(child);
				}
			}
			// 포인터 옮기기
			pointer[node] = max_point % n_sz;
		}
		// tmp_req값을 answer로 옮기기
		answer[node] += tmp_req[node];
		tmp_req[node] = 0;
	}

	// 정답 출력
	for(unsigned long i=0;i<N;i++){
		printf("%lu ",answer[i]);
	}

	return 0;
}

정답 코드 (위상정렬 알고리즘)

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

// 위상정렬 알고리즘
vector<unsigned long> topological_sort(
	vector<vector<unsigned long>> tree,
	vector<unsigned long> degree,
	const unsigned long N);
// req 계산 알고리즘
vector<unsigned long> calc_req(
	const vector<unsigned long> seq,
	const vector<vector<unsigned long>> tree,
	const unsigned long N,
	const unsigned long K);

int main(int argc, char** argv)
{
	// N, K 입력받기
	unsigned long N, K;
	scanf("%lu %lu", &N, &K);

	// 사용할 자료구조 선언
	vector<vector<unsigned long>> tree;
	vector<unsigned long> degree(N, 0);

	// data 입력받기
	for (unsigned long i=0; i<N; i++){
		// i 노드의 자녀 수 입력
		unsigned long n;
		scanf("%lu", &n);
		vector<unsigned long> tmp;
		for(int j=0; j<n; j++){
			// 자녀노드 입력
			unsigned long n2;
			scanf("%lu", &n2);
            // tree에 넣을 자녀노드를 tmp에 저장
			tmp.push_back(--n2);
			// 자녀노드의 위상 수 세기
			degree[n2]++;
		}
		// tree 갱신
		tree.push_back(tmp);
	}

	// req 계산
	vector<unsigned long> ans = calc_req(
        topological_sort(tree,degree,N),
        tree, N, K);

	// 정답 출력
	for(unsigned long i=0;i<N;i++){
		printf("%lu ", ans[i]);
	}

	return 0;
}

// 위상정렬 알고리즘
vector<unsigned long> topological_sort(
	const vector<vector<unsigned long>> tree,
	vector<unsigned long> degree,
	const unsigned long N){

	// 사용할 자료구조 선언
	queue<unsigned long> q;
	vector<unsigned long> answer;

	// 초기값 설정
	q.push(0);

	while(!q.empty()){
		// 다음 노드 불러오기
		unsigned long node = q.front();
		q.pop();
		// 노드를 q의 순서대로 정렬
		answer.push_back(node);
		// 자녀노드를 돌면서
		for (unsigned long j=0;j<tree[node].size();j++){
			unsigned long child = tree[node][j];
			// 자녀노드의 차수 갑소
			degree[child]--;
			// 위상 수가 0이 되면 q에 추가
			if (degree[child]==0) q.push(child);
		}
	}
	return answer;
}

vector<unsigned long> calc_req(
	const vector<unsigned long> seq,
	const vector<vector<unsigned long>> tree,
	const unsigned long N,
	const unsigned long K){

	// 사용할 자료구조 선언
	vector<unsigned long> answer(N, 0);

	// 초기값 설정
	answer[0]=K;

	// 위상정렬 된 순서대로 노드를 돌면서
	for (unsigned long i=0;i<seq.size();i++){
		// 다음 순서 노드 불러오기
		unsigned long node = seq[i];
		// req값 가져오기
		unsigned long req = answer[node];
		// 노드의 크기 가져오기
		unsigned long n_sz = tree[node].size();
		// leaf 노드가 아닐 경우
		if (n_sz>0){
			// 사이클 수 구하기
			unsigned long cycle = req/n_sz;
			// 사이클이 있을 경우
			if (cycle>0){
				// 자식 노드를 돌면서
				for (unsigned long i=0;i<n_sz;i++){
					// 자식노드 찾기
					unsigned long child = tree[node][i];
					// 자식노드의 answer에 cycle 추가
					answer[child] += cycle;
				}
			}
			// cycle 돌고 남은 req를 자식노드에게 하나씩 분배
			for (unsigned long i=0; i<(req % n_sz); i++){
				// 자식노드 찾기
				unsigned long child = tree[node][i];
				// 자식노드의 answer 증가
				answer[child]++;
			}
		}
	}

	return answer;
}

문제 해결 방법

1. 데이터를 입력받으면서 tree(트리구조)와 degree(위상수)를 만들어 둔다.

2. 위상정렬 알고리즘으로 노드를 정렬한다.

3. 정렬된 순서대로 노드를 돌면서 요청 수를 계산한다.