[G2] 백준 14907번 프로젝트 스케줄링 C++ 위상 정렬, 파싱, 해시맵

리뷰

 

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

오랜만에 풀어본 위상 정렬 + 파싱 문제, 재미있었다.

 

 

전역 변수

• cnt : 자신에게 들어오는 간선의 개수를 저장할 해시맵
• weights : 자신의 가중치를 저장할 해시맵
• pre_sum : 자신에게 누적된 가중치의 최대값을 저장할 해시맵
• edges : 자신으로 부터 갈 수 있는 노드를 저장한 인접 리스트 해시맵

 

함수

1. Split

vector< string > Split(const string& s)
{
	stringstream ss( s );
	vector< string > args;
	string temp = "";
	
	while ( getline( ss, temp, ' ' ) )
		args.push_back( temp );

	return args;
}

 

개행문자를 기준으로 문자열을 입력 받아 각 인자를 파싱하기 위한 함수

 

2. ParsingAndInitialize

void ParsingAndInitialize(const string& s)
{
	vector< string > args = Split( s );
	char node = args[ 0 ][ 0 ];
	weights[ node ] = stoi( args[ 1 ] );
	string conn = args.size() > 2 ? args[ 2 ] : "";
	if ( !cnt.count( node ) )
		cnt[ node ] = 0;

	for ( int i = 0; i < ( int )conn.size(); ++i )
	{
		char nextNode = conn[ i ];
		edges[ nextNode ].push_back( node );
		++cnt[ node ];
	}
}

 

파싱한 데이터를 기반으로 자료 구조의 초기값을 초기화 하기 위한 함수

 

3. Input

void Input()
{
	string s;
	while ( getline( cin, s ) )
	{
		if ( s.empty() )
			break;

		ParsingAndInitialize( s );
	}
}

 

입력 및 초기화를 담당하는 함수

 

 

문제풀이

1. Input함수를 호출하여 입력, 파싱, 초기화를 진행한다.
2. 변수 mx를 0으로 초기화 하고, 문자 타입 큐 q를 초기화한다.
3. cnt를 순회하며 value가 0인 경우 q에 key를 추가하고, 해당 노드의 pre_sum을 weights값으로 초기화한다.
4. q가 빌때까지 while루프를 수행하고, 매 루프마다 문자 변수 node에 q의 front값을 저장, pop처리한다.
5. mx를 mx와 pre_sum[node] 중 더 큰 값으로 저장한다.
6. edges[node]를 순회하고, 문자 변수 nextNode에 다음 노드를 저장한다.
7. pre_sum[nextNode]의 값을, pre_sum[node] + weights[nextNode]와 비교해 더 큰 값으로 저장한다.
8. cnt[nextNode]를 1만큼 감소시키고, 값이 0이 된 경우 q에 nextNode를 추가한다.
9. while루프가 종료된 후 mx에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 작업의 개수나 작업으로 들어오는 영문 대문자가 순차적이라는 말이 없어 해시맵을 사용해 주었다.
2. 작업을 시작하기 전에 완료해야만 하는 작업의 개수도 주어지지 않았으므로 getline으로 한줄을 입력으로 받았다.
3. stringstream을 통해 공백을 기준으로 각 요소를 파싱하였다.

 

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_map>
using namespace std;

unordered_map< char, int > cnt;
unordered_map< char, int > weights;
unordered_map< char, int > pre_sum;
unordered_map< char, vector< char > > edges;

vector< string > Split(const string& s)
{
	stringstream ss( s );
	vector< string > args;
	string temp = "";
	
	while ( getline( ss, temp, ' ' ) )
		args.push_back( temp );

	return args;
}

void ParsingAndInitialize(const string& s)
{
	vector< string > args = Split( s );
	char node = args[ 0 ][ 0 ];
	weights[ node ] = stoi( args[ 1 ] );
	string conn = args.size() > 2 ? args[ 2 ] : "";
	if ( !cnt.count( node ) )
		cnt[ node ] = 0;

	for ( int i = 0; i < ( int )conn.size(); ++i )
	{
		char nextNode = conn[ i ];
		edges[ nextNode ].push_back( node );
		++cnt[ node ];
	}
}

void Input()
{
	string s;
	while ( getline( cin, s ) )
	{
		if ( s.empty() )
			break;

		ParsingAndInitialize( s );
	}
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );

	Input();

	int mx = 0;
	queue< char > q;
	for ( const auto& [k, v] : cnt )
	{
		//cout << k << " " << v << "\n";
		if ( !v )
		{
			q.push( k );
			pre_sum[ k ] = weights[ k ];
		}
	}

	while ( !q.empty() )
	{
		char node = q.front(); q.pop();
		//cout << node << " " << pre_sum[ node ] << "\n";
		mx = max( mx, pre_sum[ node ] );

		for ( const char& nextNode : edges[ node ] )
		{
			pre_sum[ nextNode ] = max( pre_sum[ nextNode ], pre_sum[ node ] + weights[ nextNode ] );
			if ( !--cnt[ nextNode ] )
				q.push( nextNode );
		}
	}

	cout << mx;
}