BOJ2623/ C++

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

2623번: 음악프로그램

백준 온라인저지 2623번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

 

#include<iostream>
#include<queue>
#include<vector>
#define MAX 1001
using namespace std;

int indegree[MAX];
vector<int> adj[MAX];
vector<int> ans;

int n, m;

void Input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int cnt;
		int previous = 0;
		int input = 0;
		cin >> cnt >> previous;
		
		while(--cnt){
			cin >> input;
			adj[previous].push_back(input);
			indegree[input]++;
			previous = input;
		}
	}
}

void solution() {
	queue<int>q;
	for (int i = 1; i <= n; i++) 
		if (!indegree[i])
			q.push(i);

	while (!q.empty()) {
		int current = q.front();
		q.pop();
		ans.push_back(current);
		
		for (auto iter : adj[current]) {
			int next = iter;
			if (--indegree[next] == 0)
				q.push(next);
		}
	}

	if (ans.size() != n) {
		ans.clear();
		ans.push_back(0);
	}
	for (auto iter : ans)
		cout << iter << "\n";
}


int main(void) {
	Input();
	solution();
}
/*
반례 1   
q가 비었는지만 확인하면 1 2만 확인하여 단방향 그래프로 판단해버림
4 3
2 1 2
2 3 4
2 4 3

반례 2
중복입력의 케이스
3 2
2 2 3
3 2 3 1
*/

아이디어

이 문제에서 주의할 점은 중복간선이 들어왔을때에 대한 처리와 양방향 그래프가 되어 위상정렬을 적용할 수 없는 케이스를 찾아내는 것이라 생각했음

처음에는 입력 받는부분에서 중복데이터가 들어왔을때 처리를 bool check[MAX][MAX]를 이용한 dp방식으로 하였고, 양방향 그래프에 대한 처리는 진입차수가 없는 노드들만 q에 넣는 방식으로 처리했었는데 아래의 반례에 모두 꺠졌음

두가지 모두 만족 시킬수 있는 방법은 위상정렬을 이용해 정렬된 숫자들을 ans에 넣고 출력해야하는 개수와 ans에 있는 개수가 같은지 (ans.size() != n) 체크만 하면 됨 

 

엄청박살났지만 포기안함