백준 2623 음악프로그램 (c++) : 피너클

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

2623번: 음악프로그램

위상정렬 문제다.

여러가지 방법이 있지만 여기선 dfs를 이용한 위상정렬을 할것이다.

int n, m;
bool visited[1001];
vector<int> v[1001], order;
int adj[1001][1001];

사용할 변수다.

adj는 위상정렬에 사용할것이고 v는 입력받을때 order에는 정답을 넣을것이다.

cin >> n >> m;
memset(visited, false, sizeof(visited));
memset(adj, 0, sizeof(adj));
for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a;
	for (int j = 0; j < a; j++) {
		cin >> b;
		v[i].push_back(b);
	}
}

값들을 입력받고 visited와 adj를 초기화한다.

vector<int> ans = solve();
if (ans.size() == 0) cout << 0 << endl;
else for (int i = 0; i < n; i++) cout << ans[i] << '\n';

ans에 solve를 담는다. solve는 vector<int>를 반환한다.

만약 ans의 사이즈가 0이라면 (비어있다면) 0을 출력하고 아니면 ans를 출력한다.

vector<int> solve() {
	for (int k = 0; k < m; k++) {
		for (int i = 0; i < v[k].size(); i++) {
			for (int j = i + 1; j < v[k].size(); j++) {
				adj[v[k][i]][v[k][j]] = 1;
			}
		}
	}

solve는 위상정렬을 한다.

먼저 adj를 만들어야한다. adj는 a에서 b로 갈수 있는지를 의미한다.

1, 5, 2, 6가 입력받아졌다면

adj[1][5] = 1, adj[1][2] = 1, adj[1][6] = 1

adj[5][2] = 1, adj[5][6] = 1

adj[2][6] = 1

이렇게 들어간다.

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) dfs(i);
	}

그후 아직 방문하지 않은 정수를 만나면 dfs를 돌린다.

void dfs(int now) {
	visited[now] = true;
	for (int i = 1; i <= n; i++) {
		if (!visited[i] && adj[now][i] == 1) {
			dfs(i);
		}
	}
	order.push_back(now);
}

dfs다. 현재 정점을 방문한걸로 하고 방문 할수있는 모든 정점을 방문한뒤 order에 현재 정점을 넣는다.

	reverse(order.begin(), order.end());

다시 solve함수로 돌아와 dfs돌린뒤 order를 뒤집어준다.

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (adj[order[j]][order[i]]) {
				return vector<int>();
			}
		}
	}
	return order;
}

 

 

 

그후 order에 오른쪽에서 왼쪽으로 갈수 있는 정점이 있다면 비어있는 vector<int>를 반환하고 아니면 order를 반환하다.

오른쪽에서 왼쪽으로 가는 간선이 있다는 것은 사이클이 생겼다는 뜻이다.

1, 5, 6, 2, 4가 현재 order안의 숫자인데 4에서 2로 갈수있다고 생각해보자.

1, 5, 6, 2, 4, 2, 4, 2, 4, 2, 4, ..... 계속해서 반복될것이다.

그렇기에 만약 사이클이 발생한다면 바로 비어있는 벡터를 반환하는 것이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
bool visited[1001];
vector<int> v[1001], order;
int adj[1001][1001];

void dfs(int now) {
	visited[now] = true;
	for (int i = 1; i <= n; i++) {
		if (!visited[i] && adj[now][i] == 1) {
			dfs(i);
		}
	}
	order.push_back(now);
}

vector<int> solve() {
	for (int k = 0; k < m; k++) {
		for (int i = 0; i < v[k].size(); i++) {
			for (int j = i + 1; j < v[k].size(); j++) {
				adj[v[k][i]][v[k][j]] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) dfs(i);
	}
	reverse(order.begin(), order.end());
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (adj[order[j]][order[i]]) {
				return vector<int>();
			}
		}
	}
	return order;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	memset(visited, false, sizeof(visited));
	memset(adj, 0, sizeof(adj));
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a;
		for (int j = 0; j < a; j++) {
			cin >> b;
			v[i].push_back(b);
		}
	}
	vector<int> ans = solve();
	if (ans.size() == 0) cout << 0 << endl;
	else for (int i = 0; i < n; i++) cout << ans[i] << '\n';
}

전체코드다.