[Week 6] DICTIONARY self review - Yunhyunjo

[Yunhyunjo]

DICTIONARY self review

1. 해결 시도 과정

위상정렬을 위해 indegree와 ch를 선언하여 저장하고 인접리스트를 만들어 정렬을 시도하였습니다.

2. 작성한 코드와 설명

while (c--) {
		string s, p;
		fill(indegree.begin(), indegree.end(), 0);
		fill(ch.begin(), ch.end(), 0);
		vector <vector <int>> v(26);
		cin >> n >> s;
		p = s;
		ch[p[0] - 97] = 1;
		for (int i = 1; i < n; i++) {
			cin >> s;
			if (p[0] != s[0]) {
				if (ch[s[0] - 97] == 0) ch[s[0] - 97] = 1;
				indegree[s[0] - 97]++;
				v[p[0] - 97].push_back(s[0] - 97);
			}
			else {
				int pp = 1;
				while (pp < p.size() && pp < s.size()) {
					if (p[pp] != s[pp]) {
						if (ch[p[pp] - 97] == 0) ch[p[pp] - 97] = 1;
						if (ch[s[pp] - 97] == 0) ch[s[pp] - 97] = 1;
						indegree[s[pp] - 97]++;
						v[p[pp] - 97].push_back(s[pp] - 97);
						break;
					}
					pp++;
				}
			}
			p = s;
		}
		cout << topologySort(v) << endl;
	}

먼저 입력된 순서대로 비교하여 인접리스트를 만들고 indegree도 구해주었습니다.
두 단어의 0번째 값이 같을 경우에는 다음 인덱스의 해당하는 문자를 비교해주었습니다.
그렇게 구한 인접리스트를 topologySort함수에 매개변수로 넘겨주어 위상정렬을 해 출력해 주었습니다.

string topologySort(vector <vector <int>>& v) {
	string s = "";
	queue <int> q;
	for (int i = 0; i < 26; i++) {
		if (ch[i] == 1 && indegree[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		char c = x + 97;
		s += c;
		for (int j = 0; j < v[x].size(); j++) {
			if (v[x][0] == 50) return "INVALID HYPOTHESIS";
			if (--indegree[v[x][j]] == 0) q.push(v[x][j]);
		}
		v[x].clear();
		v[x].push_back(50);
	}
	if(s == "") return "INVALID HYPOTHESIS";
	for (int i = 0; i < 26; i++) {
		if (ch[i] == 0) {
			char c = i + 97;
			s += c;
		}
	}
	return s;
}

queue를 사용하여 일단 indegree값이 0인 값을 넣어주었습니다. 그 다음 bfs를 통해 위상정렬을 해 주었습니다.
순환을 막기위해 이미 정렬에 사용한 정점 리스트는 clear해준 다음 값 50을 넣어주었고, for 문을 돌때 0번째 값이 50이면 이미 정렬에 사용한 정점으로 순환된 것 이므로 바로 INVALID HYPOTHESIS를 리턴해주었습니다.
또 indegree가 0인 것이 없어 s가 비어있을 경우에도 순환이란 뜻이므로 INVALID HYPOTHESIS를 리턴해주었습니다.

3. 막힌 점 및 개선 사항

예제 입력은 정답이 제대로 나와서 정확히 어디서 틀린지를 모르겠습니다. 만약 똑같은 순서가 중복으로 나올 때 어차피 topologySort함수에서 걸러지므로 인접리스트 만들때 처리를 안해줬는데 처리하는 코드를 넣어줘야할 것 같습니다.