[프로그래머스 Level 2] 도넛과 막대 그래프(C++)

코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

생성한 정점은 나가는 엣지만 존재한다. 하지만 이 때 막대 모양에서 맨 마지막도 같은 경우가 된다. 이는 그 정점에서 나가는 엣지가 2개 이상이면 무조건 새로 생성한 정점이다. 하지만 만약에 막대 모양과 새로 생성한 정점에서 나가는 엣지가 한 개씩일 때도 있는데, 이 때 어떤 정점을 고르든 결과는 같으므로 아무거나 골라준다.

이후 8자 모양일 때는 그래프를 탐색하다가 나가는 엣지가 2개일 때일 경우고, 막대 모양은 한 정점에서 나가는 엣지가 없을 때로 구분지을 수 있다. 그리고 마지막으로 모든 정점을 돌았을 때는 도넛 모양이다.

 

#include <string>
#include <vector>
#include <memory.h>
using namespace std;

vector<int> edge[1000001];
bool checked[1000001];
int vertex;
int findShape(int a) {
	checked[a] = true;
	if (edge[a].size() == 0) {
		return 2;
	}
	if (edge[a].size() == 2) {
		return 3;
	}
	if (!checked[edge[a][0]]) {
		return findShape(edge[a][0]);
	}
	else {
		return 1;
	}
}


vector<int> solution(vector<vector<int>> edges) {
	vector<int> answer(4,0);
	for (int i = 0; i < edges.size(); i++) {
		edge[edges[i][0]].push_back(edges[i][1]);
		checked[edges[i][0]] = true;
		checked[edges[i][1]] = true;
	}
	for (int i = 1; i <= 1000000; i++) {
		if (!edge[i].empty()) {
			for (int j = 0; j < edge[i].size(); j++) {
				checked[edge[i][j]] = false;
			}
		}
	}
	int tmp = 0;
for (int i = 1; i <= 1000000; i++) {
	if (checked[i]) {
		if (edge[i].size() == 1) {
			checked[i] = false;
			tmp = i;
			continue;
		}
		vertex = i;
		checked[i] = false;
		break;
	}
}
if (vertex == 0) {
	vertex = tmp;
}
	answer[0]=vertex;
	for (int i = 0; i < edge[vertex].size(); i++) {
		int tmp = findShape(edge[vertex][i]);
		answer[tmp]++;
	}
	return answer;
}