BOJ - 2623 ) 음악프로그램

---

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

2623번: 음악프로그램

---

 

음악프로그램에 N명의 참가자가 일부 순서가 정해져있을때에 서로다른 M가지의 일부순서를 만족하는

 

하나의 전체순서를 구하는 전형적인 위상정렬문제이다. 

 

만약 그래프에 사이클이 생겼을때에는 전체 N을 방문하지 않고 끝나므로, Indegree배열에 0이 아닌값이

 

저장되게되므로 위상정렬이 끝난후에 이부분을 체크해준다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<Integer> al[];
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		al = new ArrayList[n];
		int indegree[] = new int[n];
		for(int i = 0 ; i < n ; i ++) al[i] = new ArrayList<>();
		for(int i = 0 ; i < m ; i ++) {
			st = new StringTokenizer(br.readLine());
			int size = Integer.parseInt(st.nextToken());
			int first = Integer.parseInt(st.nextToken())-1;
			for(int j = 0 ; j < size-1 ; j ++) {
				int second = Integer.parseInt(st.nextToken())-1;
				al[first].add(second);
				indegree[second]++;
				first = second;
			}
		}
		ArrayList<Integer> res = new ArrayList<>();
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		for(int i = 0 ; i < n ; i ++) {
			if(indegree[i] == 0) {
				dq.add(i);
				res.add(i);
			}
		}
		
		while(!dq.isEmpty()) {
			int now = dq.poll();
			for(int i = 0 ; i < al[now].size(); i++) {
				int cur = al[now].get(i);
				indegree[cur]--;
				if(indegree[cur] == 0) {
					dq.add(cur);
					res.add(cur);
				}
			}
		}
		
		boolean isAns = true;
		for(int i = 0 ; i  < n ; i++) {
			if(indegree[i] != 0) isAns = false;
		}
		if(isAns) {
			for(int i = 0 ; i < n;i++) {
				System.out.println(res.get(i)+1);
			}
		}else {
			System.out.println(0);
		}
		
	}
}

---

 

 

 

 

---

+ 2020-03-24 내용추가 )

위상정렬은 2가지로 구현할 수 있는데, 한가지는 BFS+진입차수를이용한 방법이고 

또다른 한가지는 인접행렬+DFS+사이클검사를 이용한 방법이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int map[][],indegree[],n,m;
	static boolean visit[];
	static boolean finish[];
	static boolean isAns= true;
	static Stack<Integer> s = new Stack<Integer>();
	
	private static void dfs(int i) {
		visit[i] = true;
		for(int j = 0 ; j < n ; j++) {
			if(map[i][j] ==1 && !visit[j]) {
				dfs(j);
			}else if(map[i][j]==1 &&!finish[j]) {
				isAns = false;
			}
		}
		finish[i] = true;
		s.push(i+1);
	}
	public static void main(String[] args)  throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		visit = new boolean[n];
		finish = new boolean[n];
		indegree = new int[n];
		for(int i = 0 ; i < m ; i++) {
			st =new StringTokenizer(br.readLine());
			int size = Integer.parseInt(st.nextToken());
			int f = Integer.parseInt(st.nextToken())-1;
			for(int j = 0 ; j < size -1 ; j++) {
				int e = Integer.parseInt(st.nextToken())-1;
				map[f][e] =1; // f에서 e로가는 길이있다.
				f= e;
				indegree[e]++;
			}
		}
		for(int i = 0 ; i < n ; i ++) {
			if(indegree[i]==0) dfs(i);
		}
		if(isAns) {
			while(!s.isEmpty()) {
				System.out.println(s.pop());
			}
		}else {
			System.out.println(0);
		}
	}
	
}

 

---

 

인접행렬을 받은뒤에 시작노드에서 끝노드로 갈수있다면 인접행렬에 1을 표시해준다.

 

인접행렬의 세로의 합은 진입차수를 의미하므로, 세로의 합이 0인 즉 진입차수가 0인 노드부터 시작하여 DFS로 

 

노드들을 순회한다. 이때 결정되는 순서는 문제에서 정의된 순서를 따를수밖에 없으므로 진입차수가 0인부분부터

 

모두 실행한다면 문제조건을 만족하는 위상정렬 결과가 나올것이다..

 

중간에 사이클을 확인하는데에 2번 실수를하였는데, DFS도중에 방문체크말고, 이 노드가 지금 순회하는 경로에서 

 

2번째 방문하는것을 체크해주어야 했다. 따라서 STACK에 넣기 전에 한경로에서 체크여부를 표시해주는 

 

배열을 따로잡아야했다. 만약 방문되었는데, FINISH배열이 FALSE라면, 한 DFS에서 2번 탐색한 것이므로

 

그래프가 있어서 0 을 출력한다.