[SWEA] #1267 - 작업순서

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

해야 할 V개의 작업이 있다. 이들 중에 어떤 작업은 특정 작업이 끝나야 시작할 수 있으며, 이를 선행 관계라 하자.

이런 작업의 선행 관계를 나타낸 그래프가 주어진다.

이 그래프에서 각 작업은 하나씩의 정점으로 표시되고 선행 관계는 방향성을 가진 간선으로 표현된다.

단, 이 그래프에서 사이클은 존재하지 않는다 (사이클은 한 정점에서 시작해서 같은 정점으로 돌아오는 경로를 말한다).

아래 그림은 이런 그래프의 한 예다.

 

이 그래프에서 작업 1은 작업 4가 끝나야 시작할 수 있다.

작업 6은 작업 5와 작업 7이 끝나야 할 수 있다.

이 그래프에서는 사이클이 없다.
 
김 과장은 선행 관계가 주어진 작업 군을 한 번에 하나의 작업씩 처리해서 다 끝내려 한다.

위에서 예를 든 작업 군에 대해서 이런 일을 한다면 아래의 순서로 처리할 수 있다.
 
8, 9, 4, 1, 5, 2, 3, 7, 6
 
또한 아래의 순서도 가능하다.
 
4, 1, 2, 3, 8, 5, 7, 6, 9
 
아래의 순서는 가능하지 않다.
 
4, 1, 5, 2, 3, 7, 6, 8, 9
 
이 순서에서는 작업 5가 작업 8보다 먼저 처리되는데, 위 그래프에서 주어진 선행 관계에서는 작업 5는 작업 8이 끝나야 시작할 수 있어 이 순서로 끝내는 것은 가능하지 않다.
 
V개의 작업과 이들 간의 선행 관계가 주어질 때, 한 사람이 한 번에 하나씩 일을 할 수 있는 작업 순서를 찾는 프로그램을 작성하라.

가능한 작업 순서는 보통 여러 가지가 있으므로 여러분은 이들 중 하나만 제시하면 된다.

 

[제약사항]

사이클이 있는 그래프는 입력에서 주어지지 않으므로 이런 경우에 대한 에러 처리는 고려하지 않아도 좋다.

사이클이 없는 그래프에서 가능한 순서는 항상 존재한다.

 

💡 아이디어

---

이 문제는 진입 차수를 이용해 문제를 해결할 수 있다.

진입 차수는 해당 노드로 들어오는 간선의 개수이다.

즉, 진입 차수가 0이면 해당 노드로 이어진 간선은 없다는 것을 의미한다.

그렇기 때문에 진입 차수가 0인 것들을 모두 Queue에 넣은 다음에 이어진 간선을 따라가며 도착한 노드의

진입 차수를 -1 시켜준다. 만약 -1을 했을 때 해당 노드의 진입 차수가 0이면 Queue에 넣어준다.

이 과정을 Queue가 빌 때까지 반복하면 작업순서를 구할 수 있다.

사이클이 있는 그래프는 입력에서 주어지지 않기 때문에 따로 처리를 할 필요는 없다.

 

💡 소스코드

---

package SWEA;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA_P1267_작업순서 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1267_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;

		for (int TC = 1; TC <= 10; TC++) {
			sz = new StringTokenizer(br.readLine());

			int V = Integer.parseInt(sz.nextToken());// Vertex 개수
			int E = Integer.parseInt(sz.nextToken());// Edge 개수

			int[][] G = new int[V + 1][V + 1];//인접행렬 선언
			int[] InDegree = new int[V + 1];//진입차수 선언
			
			Queue<Integer> queue = new LinkedList<Integer>();//Queue선언

			String[] str = br.readLine().split(" ");//한 줄 입력

			for (int i = 0; i < E * 2; i += 2) {
				G[Integer.parseInt(str[i])][Integer.parseInt(str[i + 1])] = 1;// 연결된 Vertex는 1
				InDegree[Integer.parseInt(str[i + 1])]++;//간선을 받는 Vertex는 진입차수 + 1
			}

			for (int j = 1; j < G.length; j++)//진입차수가 0인 Vertex는 Queue에 Add
				if (InDegree[j] == 0)
					queue.add(j);

			System.out.print("#" + TC + " ");

			while (!queue.isEmpty()) {//Queue가 빌 때까지 반복
				int node = queue.poll();//Queue에서 하나 꺼내서 출력
				System.out.print(node + " ");

				for (int k = 1; k <= V; k++) {
					if (G[node][k] == 1) {//Q에서 나가는 Edge가 있다면
						InDegree[k]--;//InDegree값 -1
						if (InDegree[k] == 0)//InDegree값이 0이면 들어오는 간선이 없다는 의미이므로
							queue.add(k);// Queue에 추가
					}
				}
			}
			
			System.out.println("");
		}
		br.close();
	}
}

 

💡 결과

---