자료구조 '그래프'를 이용한 문제 : 만남(Meeting)

카테고리 없음

2019. 2. 10. 02:55

01 . 문제 해결 과정


01) 각 시작 정점으로부터 임의의 정점까지 걸리는 시간을 저장하고 그 중 최댓값을 구한다.


02) 각각의 정점에서 구한 최댓값들 중 최솟값을 가지는 정점의 id와 그 최솟값을 출력한다.


- 위 경우를 예로 들어보자.

a에서 e까지 걸리는 시간을 구한다(1) -> m에서 e까지 걸리는 시간을 구한다(1)-> k에서 e까지 걸리는 시간을 구한다(7) -> 최댓값은 7

e 이외의 모든 정점들에 대해서도 최댓값을 구한다.

최댓값들 중 최소값을 가지는 정점은 f이며, 이 정점에서의 최댓값은 4이다.


02. 자료구조 정의


01) Vertex -> Entitiy Class

- string id : 이름

- list<Vertex*> adj : 인접 Vertext의 포인터 리스트

- map<string, int> time : 특정 Vertex의 이름이 key, 그 특정 Vertex까지 걸리는 시간이 value인 map

- int maxTime : time중 최대 value

- bool isPut : 현재 Vertex가 큐에 들어갔는지 아닌지의 여부


02) Graph -> Control Class

- int N : 정점의 수

- vector<Vertex*> vertexes : 모든 정점들의 포인터를 가지고 있는 벡터

- vector<string> starters : 시작 정점들의 이름을 가지고 있는 벡터


03. BFS(Breath First Searching)Queue


이 문제에서는 시작 정점으로부터 임의의 정점까지의 최소거리를 계산해야 하므로 DFS(Depth First Searching)을 사용하면 안되고 Queue를 활용한 BFS방식으로 그래프를 순회해야 한다.


시작 정점에서부터 시작하여, 인접 정점들에 대하여 큐에 넣은적이 없다면 큐에 넣고, 하나씩 앞에서부터 뽑아 순회한다.


04. 코드

#include <bits/stdc++.h>
using namespace std;

class Graph;

// 정점
class Vertex {
friend class Graph;
private:
	string id;
	list<Vertex*> adj;
	map<string, int> time;
	int maxTime;
	bool isPut;
public:
	// 생성자
	Vertex(string id) : id(id),
		isPut(false), maxTime(0) {}
};

// 정점들로 이루어진 그래프
class Graph {
private:
	int N;
	vector<Vertex*> vertexes;
	vector<string> starters;
public:
	// 생성자
	Graph(ifstream &inp);
	// id가 id인 Vertex의 pointer를 얻음
	Vertex* getPVertex(string id);
	// 모든 Vertex의 isPut를 false로 셋팅
	void reset();
	// 각 시작점에서부터 BFS(queue 사용)방식으로 모든 Vertex를 순회한다.
	void traverse();
	// 출력 형식에 맞게 출력한다.
	void print(ofstream &out);
	// 소멸자
	~Graph();
};

Graph::Graph(ifstream &inp) {
	int N;
	string id1, id2, id3;

	// 정점의 갯수를 입력받는다
	inp >> N;
	this->N = N;
	// 시작 정점의 id를 입력받는다
	inp >> id1 >> id2 >> id3;
	this->starters.push_back(id1);
	this->starters.push_back(id2);
	this->starters.push_back(id3);

	// N번 반복
	while(N--) {
		// 정점과 그 정점에 대한 인접정점 포인터로 사용될 지역변수 선언
		Vertex *pVertex, *pAdj;
		string id;
		inp >> id;
		// 만약 id가 id인 정점이 없으면
		if(!(pVertex = getPVertex(id))) {
			// 새로운 정점을 만들고
			pVertex = new Vertex(id);
			// vertexes 벡터에 넣기
			vertexes.push_back(pVertex);
		}
		// 인접정점 입력
		while(inp >> id && id != "$") {
			// 만약 id가 id인 정점이 없으면
			if(!(pAdj = getPVertex(id))) {
				// 새로운 정점을 만들고
				pAdj = new Vertex(id);
				// vertexes 벡터에 넣기
				vertexes.push_back(pAdj);
			}
			// 이미 정점이 있었거나 새로 만든 인접정점 포인터를
			// adj 벡터에 넣기
			pVertex->adj.push_back(pAdj);
		}
	}

	// 각 정점의 time map에 (시작 지점들의 아이디):0 넣기
	for(auto it=vertexes.begin(); it!=vertexes.end(); ++it) {
		for(auto it2=starters.begin(); it2!=starters.end(); ++it2)
			(*it)->time.insert(pair<string, int>((*it2), 0));
	}
}

Vertex* Graph::getPVertex(string id) {
	vector<Vertex*>::iterator it;
	for(it=vertexes.begin(); it!=vertexes.end() && !((*it)->id==id); ++it) ;
	if(it!=vertexes.end())
		return *it;
	return NULL;
}

void Graph::reset() {
	for(auto it=vertexes.begin(); it!=vertexes.end();
		++it) (*it)->isPut = false;
}

// queue를 이용한 BFS 순회
void Graph::traverse() {
	// 각 시작 정점들에서부터 시작
	for(auto it=starters.begin(); it!=starters.end(); ++it) {
		string id = *it;
		Vertex *starter = getPVertex(id), *pVertex;
		// 정점의 포인터들이 들어갈 큐
		queue<Vertex*> q;

		// 먼저 시작 정점을 넣고
		q.push(starter);
		// 시작 정점의 방문여부를 true로 셋팅
		starter->isPut = true;
		// pVertex에 방금 넣은 시작 정점의 포인터를 대입
		pVertex = q.front();
		// pop
		q.pop();
		
		// 시작정점의 인접정점들을 모두 큐에 넣고 큐 삽입여부를 true로 셋팅
		for(auto it2=pVertex->adj.begin(); it2!=pVertex->adj.end(); ++it2) {
			q.push(*it2);
			(*it2)->isPut = true;
		}

		// 더 이상 방문할 정점이 없을 때까지
		while(q.size()!=0) {
			// 하나를 뽑는다 (도로를 지나 이 정점에 방문한 상태)
			pVertex = q.front();
			q.pop();
			// 도로를 하나 지났으므로 시작정점으로부터의 시간을 1 더함
			pVertex->time[id] += 1;
			// 인접정점들에 대하여
			for(auto it3=pVertex->adj.begin(); it3!=pVertex->adj.end(); ++it3) {
				// 큐에 들어가지 않았다면
				if(!((*it3)->isPut)) {
					// 시작 정점으로부터 현재 정점까지 걸리는 시간 + 2
					// 로 인접정점의 시간을 셋팅
					(*it3)->time[id] = pVertex->time[id] + 2;
					// 큐에 넣음
					q.push(*it3);
					(*it3)->isPut = true;
				}
			}
		}
		// 모든 정점들에 대하여 isPut을 초기화 하고
		// 다음 시작 정점에서부터 다시 시작
		reset();
	}

	// 모든 정점들에 대하여 3개의 시간들 중 최댓값 선정
	for(auto it=vertexes.begin(); it!=vertexes.end(); ++it) {
		int max=0;
		for(auto it2=(*it)->time.begin(); it2!=(*it)->time.end(); ++it2)
			max = (it2->second > max) ? it2->second : max;
		(*it)->maxTime = max;
	}

	// 정점들의 순서를 정렬
	sort(vertexes.begin(), vertexes.end(), [](Vertex *A, Vertex *B){
		// 최댓값이 작은 순서대로
		if(A->maxTime != B->maxTime)
			return A->maxTime < B->maxTime;
		// 최댓값이 같다면 알파벳 순서대로
		else
			return A->id.compare(B->id) < 0;
	});
}

void Graph::print(ofstream &out) {
	out << vertexes[0]->id << endl;
	out << vertexes[0]->maxTime;
}

Graph::~Graph() {
	for(auto it=vertexes.begin(); it!=vertexes.end(); ++it)
		delete(*it);
}

int main(void)
{
	ifstream inp("meeting.inp");
	ofstream out("meeting.out");
	Graph graph(inp);
	graph.traverse();
	graph.print(out);

	inp.close();
	out.close();
	return 0;
}