[2623] 음악프로그램 - 위상정렬 ★★☆ / 복습 ○

 

[ 문제 ] : https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

---

[ 문제 접근 ]

위상정렬 문제라는건 알겠는데 입력 받는게 난해했다.

- 기존에 알던 방식으로 입력을 받는게 아니라서 당황했다.

---

[ 최종 코드 ]

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

using std::cout; using std::cin;
using std::vector;

// 위상정렬 문제 DFS / BFS로 풀이 가능.

int N, M;
int a, b, c;
vector<int> adjancent[1001];
int indegree[1001];
int input[1001];

void topologicalSort() {
	vector<int> answer;
	std::queue<int> q;

	// indegree 가 0인 작업 넣는다.
	for (int i = 1; i < N + 1; i++) {
		if (!indegree[i]) q.push(i);
	}
	while (!q.empty()) {
		int cur = q.front();
		answer.push_back(cur);
		q.pop();
		for (size_t i = 0; i < adjancent[cur].size(); i++) {
			int next = adjancent[cur][i];
			if ((--indegree[next]) == 0) { // 하나 감소 시켰는데 indegree가 0이면 q에 푸쉬.
				q.push(next);
			}
		}
	}
    // 정답에 모든 노드가 없을때 불가능이라고 판단하고 0 출력
	if (answer.size() != N) {
		cout << 0 << '\n';
		return;
	}
	for (auto elem : answer) {
		cout << elem << '\n';
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M;
	while (M--) {
		cin >> a;
		for (int i = 0; i < a; i++) {
			cin >> input[i];
		}
		for (int i = 0; i < a - 1; i++) {
			adjancent[input[i]].push_back(input[i + 1]);
			indegree[input[i + 1]]++;
		}
	}
	topologicalSort();

	return 0;
}

---

[ Key Point ]

 

👉 일단 나는 아래와 같이 입력 받았다.

cin >> a;
for (int i = 0; i < a; i++) {
	cin >> input[i];
}
for (int i = 0; i < a - 1; i++) {
	adjancent[input[i]].push_back(input[i + 1]);
	indegree[input[i + 1]]++;
}

근데 formal 한 느낌이 아니라 야매 같은 느낌이 들어 다른 사람들 어떻게 받았나 찾아봤다. 

 

        for (int i = 0; i < sNum-1; i++) {
            cin >> s2;
            v[s1].push_back(s2);
            inDeg[s2]++;
            s1 = s2;
        }

위에 같이 받는게 조금 더 좋을것 같다.

 

👉 문제에서 "만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다."

라고 조건이 주어졌다. 뭘 물어보는걸까 고민하다 그래프에 사이클이 존재하는지 물어보는건가 싶었다.

 

그래서 다른 사람들의 풀이를 보니 그냥 queue에 모든 정점이 담기지 않았으면 0 을 출력하게끔 해놨다.

( 이 부분은 복습할때 자세히 봐야겠다. )

---

[ 다른 사람 풀이 ]

 

ref : https://scarlettb.tistory.com/66