[백준 2623/C++] 음악 프로그램

1. 문제 / 난이도 : GoldⅡ

www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

---

2. 풀이 및 코드 설명

처음에는 어떻게 풀어야하지...? 하고 고민하다가 결국 알고리즘 분류에 위상정렬이라는 키워드가 있는 것을 보고 간단한 위상정렬 구현으로 쉽게 풀었다.

순서가 정해져 있는 노드들을 전부 방문해야 한다면 => 위상 정렬을 사용할 수 있다는 점을 잊지 말자!

(1) 초기화 및 설정

	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev; // i가 0이라면 맨 처음 값이므로 prev 초기화
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1; // 진입 vertex 수 cnt 증가
				arr[prev].push_back(current); // prev -> current로 이어진 그래프 생성
				prev = current; // prev 갱신
			}
		}
	}

• arr : 각 노드마다 연결된 노드들의 정보들을 저장
• cnt : 위상정렬을 구현하기 위한 배열. 각 노드당 진입 vertex의 개수를 저장

(2) 큐 초기값

queue<int> q; // 위상정렬 큐
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) { // 아직 방문하지 않았고, 진입 vertex 수가 0이라면
			q.push(i); // 해당 노드 큐에 추가
			visit[i] = 1; // visit값 갱신
		}
	}

(3) 위상정렬

	while (!q.empty()) {
		int current = q.front(); // 현재 노드
		q.pop();
		result.push_back(current); // result 배열에 추가

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--; // 현재 노드와 연결된 노드 모두 진입 vertex 수 하나씩 감소
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) { // 갱신된 노드들 중 진입 vertex 수가 0이고 아직 방문하지 않았다면
				q.push(i);
				visit[i] = 1;
			}
		}
	}

• 큐가 빌 때까지 위상정렬 진행

(4) 출력

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}

• result 크기와 N이 같지 않다는 것 : 중간에 순환이 생겨 위상정렬이 제대로 이루어지지 않았다는 것 = 순서를 정할 수 없다는 말
• 위의 조건이 아닐때는 result 순서대로 출력

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <queue>
using namespace std;

int N, M, K;
vector<vector<int>> arr(1001);
int cnt[1001];
int visit[1001];
vector<int> result;

int main() {
	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev;
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1;
				arr[prev].push_back(current);
				prev = current;
			}
		}
	}

	queue<int> q;
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) {
			q.push(i);
			visit[i] = 1;
		}
	}
	
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		result.push_back(current);

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--;
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) {
				q.push(i);
				visit[i] = 1;
			}
		}
	}

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}
}