1267번 : 작업순서 [Java]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN

SW Expert Academy

 

해결 방안

위상 정렬을 사용한다.

1. 인접행렬을 위한 배열과 진입 차수 저장을 위한 배열을 만들어 입력받는다.

2. 큐에 진입차수가 0인 노드들을 저장한다.

3. 큐가 빌때까지

4. 노드를 꺼내 출력 후, 그 노드에 연결된 노드들의 진입 차수를 하나 줄이고

5. 진입 차수가 0이 된다면 큐에 넣는다.

 

전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = 10;
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");
			int V = sc.nextInt();
			int E = sc.nextInt();
			int[] indegree = new int[V];
			int[][] adj = new int[V][V];
			for (int i = 0; i < E; i++) {
				int from = sc.nextInt() - 1;
				int to = sc.nextInt() - 1;
				adj[from][to] = 1;
				indegree[to]++;
			}
			Queue<Integer> queue = new LinkedList<Integer>();
			for (int i = 0; i < V; i++) {
				if (indegree[i] == 0)
					queue.add(i);
			}

			while (!queue.isEmpty()) {
				int node = queue.poll();
				sb.append(node + 1).append(" ");
				for (int i = 0; i < V; i++) {
					if (adj[node][i] == 1) {
						indegree[i]--;
						if (indegree[i] == 0)
							queue.add(i);
					}
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}