[SW expert Academy] SWEA 1267번 작업순서 자바(Java) 위상정렬

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [SW expert Academy] SWEA 1267번 작업순서 자바(Java)

1) 난이도 : D6

 

2) 문제번호 : 1267번

 

3) 문제 출처

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

SW Expert Academy

 

2. 문제

해야 할 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개의 작업과 이들 간의 선행 관계가 주어질 때, 한 사람이 한 번에 하나씩 일을 할 수 있는 작업 순서를 찾는 프로그램을 작성하라.

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

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

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

 

3. 제약사항

- 그래프에서 정점의 총 수 V는 5≤V≤1000.

4. 입력

10개의 테스트 케이스가 주어진다.

20줄에 걸쳐, 두 줄에 테스트 케이스 하나씩 제공된다.

각 케이스의 첫줄에는 그래프의 정점의 총 수 V와 간선의 총 수 E가 주어진다.

그 다음 줄에는 E개 간선이 나열된다.

간선은 간선을 이루는 두 정점으로 표기된다.

예를 들어, 정점 5에서 28로 연결되는 간선은 “5 28”로 표기된다.

정점의 번호는 1부터 V까지의 정수값을 가지며, 입력에서 이웃한 수는 모두 공백으로 구분된다.

 

5. 출력

총 10줄에 10개의 테스트케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 작업 순서를 기록한다.

작업 순서는 V개 정수를 공백을 사이에 두고 나열하는 것이다.

 

6. 풀이

- 진입차수가 0이라면 큐에 넣어서, 큐가 빌 때까지 while문을 돌려 인접행렬의 값이 1이라면 진입차수를 1 줄이고 진입차수가 0이라면 다시 큐에 넣으면 된다.

7. 소스 코드

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

public class Main {
    static int V; // 정점의 개수
    static int E; // 간선의 개수
    static int[][] adj; // 인접행렬
    static int[] indegree; // 진입차수
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int tc=1;tc<=10;tc++) {
        	V = sc.nextInt(); // 정점의 개수
        	E = sc.nextInt(); // 간선의 개수
        	
        	adj = new int[V][V]; // 인접행렬
        	indegree = new int[V]; // 진입차수
        	
        	//인접행렬 입력
        	for(int i=0;i<E;i++) {
        		int start = sc.nextInt()-1;
        		int end = sc.nextInt()-1;
        		
        		adj[start][end] = 1;
        		indegree[end]++;
        	}
        	
        	//큐 생성해서
        	Queue<Integer> que = new LinkedList<Integer>();
        	
        	//indegree에서 진입차수가 0이라면 큐에 넣어
        	for(int i=0;i<V;i++) {
        		if(indegree[i]==0) que.add(i);
        	}
        	System.out.print("#"+ tc + " ");
        	
        	//큐 빌 때까지 반복해서
        	while(!que.isEmpty()) {
        		// 큐에 든거 하나 꺼내서
        		int node = que.poll();
        		System.out.print((node+1) + " ");
        		//인접행렬이 1이라면 진입차수를 1 줄이고, 
        		for(int i=0;i<V;i++) {
        			if(adj[node][i]==1) {
        				indegree[i]--;
        				//진입차수가 0이라면 다시 넣어
        				if(indegree[i]==0) que.add(i);
        			}
        		}
        	}
        	System.out.println();
        }
        
    }
}

---

DAG(Directed Acyclic Graph) : 유향 비사이클 그래프

Tree는 DAG이다 (O)
DAG는 Tree이다 (X)

위상정렬의 슈도코드(QUEUE 사용)

1. 진입 차수가 0인 모든 노드를 큐에 삽입
2. 큐가 공백상태가 될 때까지 반복
1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거(연결된 노드의 진입 차수를 감소 시킨다.)
2) 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다.

3. 큐에서 꺼내지는 순서(큐에서 들어오는 순서)가 결과다.