[SWEA] 1267. 작업순서

문제

1267. [S/W 문제해결 응용] 10일차 - 작업순서
작업의 선행 관계를 나타낸 그래프가 주어진다. 이때, 꼭 선행 작업을 해야 다음 작업을 할 수 있다. 작업 순서를 출력해라.

어려웠던 문제.. 처음부터 힌트를 듣고 풀어서 순전히 내 실력으로만 했으면 어떻게 됐을 지 궁금하다🤔
아무튼 풀긴 했으나 코드가 썩 맘에 들진 않는다.

풀이

출력방식이 #test_case a b c d e f ...였기 때문에 test_case를 먼저 출력하고 방문할 때마다 정점의 번호를 출력했다.

• 이전 정점의 개수 prevCnt = 선행 작업의 수
• 이후 정점의 개수 nextCnt= 내가 선행 작업인 작업의 수
• 간선 쌍 next : a->b 인 간선들을 저장!

계속해서 선행 작업이 없는 정점만 출력한다! 이때, 출력된 정점과 연결된 정점들은 prevCnt--; 해준다.

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int V = sc.nextInt();
			int E = sc.nextInt();
			
			int [] prevCnt = new int[V+1]; // 이전 정점의 개수 
			int [] nextCnt = new int[V+1]; // 이후 정점의 개수 
			int [][] next = new int[V+1][E]; // 간선 쌍 저장 (비효율적인 2차원 배열..)
			
			int a, b;
			for (int i=0; i<E; i++) {
				a = sc.nextInt(); b = sc.nextInt();
				next[a][nextCnt[a]] = b; // 간선 쌍 저장 
				nextCnt[a]++;
				prevCnt[b]++;
			}
		
			System.out.printf("#%d", test_case);
			
			for (int i=0; i<V; i++) {
				for (int j=1; j<=V; j++) {
					if (prevCnt[j] == 0) { // 이전 정점이 없다면 출력 
						System.out.printf(" %d", j);
						prevCnt[j] = -1; // 방문 표시 
						for (int k=0; k<nextCnt[j]; k++) {
							prevCnt[next[j][k]]--; // 연결돼있는 정점들의 이전 정점 개수를 하나 줄여줌 
						}
					}
				}
			}
			
			System.out.println();
		}
	}
}

아쉬운 점

• 정점의 최대 숫자가 V라고 가정했다. 다행이 여기선 범위에 맞게 주어졌다. V=3 인데 {5,6,7} 이랬으면🤦‍♀️ (왜냐면 prevCnt[j] == 0 으로 체크하는데, 주어진 정점인지 아닌지 확인하는 절차가 필요해짐)
• prevCnt, nextCnt를 hash를 사용했어도 괜찮았을 듯 ! 딱 사용하는 정점만 저장할 수 있도록!
  -> 정점의 최대 숫자 = 범위V 였기 때문에 다행이 메모리의 크나큰 낭비는 없었다.
• next를 2차원 배열 말고 ArrayList를 활용하고 싶었다. C++의 vector는 배열로 하기 쉬웠는데 여기선 뭔가 꼬였다 ㅜㅜ 그 결과 사용하는 것에 비해 너무 큰 배열을 만들게 되었다.