코딩 테스트 [그래프] - 줄 세우기

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어 두 학생의 키를 비교하는 방법을 사용하기로 했다. 그나마도 모든 학생을 비교해 본 것이 아니라 일부 학생들의 키만을 비교해 봤다. 일부 학생들의 키를 비교한 결과가 주어졌을 때 줄을 세우는 프로그램을 작성하시오.

(시간 제한 2초)

---

입력

1번째 줄에 학생의 수 N(1 ≤ N ≤ 32,000), 키를 비교한 횟수 M(1 ≤ M ≤ 100,000)이 주어진다. 그다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미다. 학생들의 번호는 1번부터 N번이다.

출력

1번째 줄부터 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지일 경우에는 아무거나 출력한다.

예제 입력
4 2	// 노드 개수, 에지 개수
4 2
3 1

예제 출력
4 2 3 1

---

1단계 - 문제 분석하기

학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다 생각했을 때 노드의 순서를 도출하는 기본적인 문제이다. 특히 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 전제와 동일하다.

2단계 - 손으로 풀어 보기

1 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트한다.

2 다음 순서에 따라 위상 정렬을 수행한다.

1. 진입 차수가 0인 노드를 큐에 저장한다.
2. 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.
4. 큐가 빌 때까지 1 ~ 3을 반복한다.

3단계 - sudo코드 작성하기

N(학생 수) M(비교 횟수) A(데이터 저장 인접 리스트) indegree(진입 차수 배열)

학생 수만큼 인접 리스트 초기화
진입 차수 배열 초기화

for(비교 횟수만큼 반복)
{
	인접 리스트 데이터 저장
    진입 차수 배열 초기 데이터 저장
}

큐 생성
for(학생 수)
{
	진입 차수 배열의 값이 0인 노드 큐에 삽입
}

while(큐가 빌 때까지)
{
	현재 노드 = 큐에서 poll
    현재 노드값 출력
    
    for(현재 노드에서 갈 수 있는 노드의 개수)
    {
    	타깃 노드 진입 차수 배열 --
        if(타깃 노드의 진입 차수가 0이면)
        {
        	큐에 타깃 노드 추가하기
        }
    }
}

4단계 - 코드 구현하기

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

public class Q53 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        ArrayList<Integer>[] A = new ArrayList[N+1];
        for(int i = 1; i < N+1; i++){
            A[i] = new ArrayList<Integer>();
        }
        int[] indegree = new int[N+1];

        for(int i = 0; i < M; i++){
            int S = sc.nextInt();
            int E = sc.nextInt();
            A[S].add(E);
            indegree[E]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i < N+1; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }

        while(!queue.isEmpty()){
            int now = queue.poll();
            System.out.print(now + ", ");
            for(int i = 0; i < A[now].size(); i++){
                indegree[A[now].get(i)]--;
                if(indegree[A[now].get(i)] == 0){
                    queue.add(A[now].get(i));
                }
            }
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편