2252번 줄 세우기 G3

 

 

 문제의 내용은 위와 같다.

 

중요한 것은 N과 M을 입력 받은 후,

 

M번 입력을 받는데, 그때 입력받는 두 번호가 비교하는 학생의 번호이고, 앞에 입력받는 번호의 학생이 

 

뒤에 입력받는 학생보다 앞에 선다는 것이다.

 

즉 

 

3 2 

1 3

2 3 이면

 

1번 학생은 3번 학생의 앞에,

 

2번 학생은 3번 학생의 앞에 줄을 선다는 것이다.

 

1번과 2번 학생의 순서는 상관없으므로 

 

답은 1 2 3 또는 2 1 3이 될 수 있다.

 

이를 위해 우선 Linked List배열을 생성한다. 이 때 받을 인자는 Integer이다. 

 

그 후 N의 크기만큼의 배열을 생성하고,

 

각각 초기화를 시켜준다.

 

이후 순서 비교를 위해 입력받은 인자를 리스트에 입력한다.

 

순서를 정해준 것이기 때문에 유향 그래프라고 할 수 있다.

 

 

이런 느낌.

 

또한 학생들의 수 크기의 일차원 배열을 만든다.

 

이 배열에는 진입 차수를 입력한다.

 

위까지의 과정은 다음과 같다.

 

LinkedList<Integer> [] list=new LinkedList[n+1]// 인덱스 가리키기 쉽게+1해준다
arr=new int[n+1]//역시 +1

for(int i=0;i<=n;i++){
	list[i]=new LinkedList<>();
    }
Queue<Integer> q= new LinkedList<>();
for(int i=0;i<m;i++){
	StringTokenizer st = new StringTokenizer(br.readLine());
    int s=Integer.parseInt(st.nextToken());
    int g=Integer.parseInte(st.nextToken());
    list[s].add(g);
    arr[g]++;
    }

 

다음으로는 진입 차수가 0인 학생을 선택하여 Queue에 넣는다.

 

즉, 해당 학생 앞에 서야할 학생이 딱히 없는 경우이다.

 

for(int i=1;i<=n;i++){
	if(arr[i]==0){
    	q.add(i);
        }
    }

 

간단하게 진입차수가 0인 학생을 뽑는다.

 

다음으로는 Queue가 공백상태가 될 때까지 

 

학생을 뽑고 넣으며 진입차수를 줄여가면된다.

 

이때, 진입 차수가 새롭게 0이 되는 경우와 기존에 0이 되는 경우를 구분하기 위해 

 

뽑자마자 진입차수 배열에서 똑같이 -1해준다.

 

while(!q.isEmpty()){
	int tmp=q.poll();
    bw.write(tmp+" ");
    arr[tmp]--;
    for(int i=0;i<list[tmp].size();i++){
    	arr[list[tmp].get(i)]--;
        if(arr[list[tmp].get(i)]==0){
        	q.add(list[tmp].get(i));
            }
        }
    }

 

이렇게 하면 새롭게 진입 차수가 0이된 학생과 기존의 0이었던 학생을 간단하게 구분할 수 있다.