[백준 문제 풀기] 2252번: 줄 세우기 (위상정렬, 자바)

문제 : https://www.acmicpc.net/problem/2252

 

문제
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

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

학생들의 번호는 1번부터 N번이다.

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

 

예제 입력, 출력

	예제 입력	예제 출력
1	3 2 1 3 2 3	1 2 3
2	4 2 4 2 3 1	4 2 3 1

 

사용 알고리즘

위상 정렬 (Topology Sort)

 

코드 (자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 줄세우기 : https://www.acmicpc.net/problem/2252
// 위상정렬

// ※ 고려사항
// 그래프가 모두 연결이 되어있지 않을수 있다. 즉, 시작점이 여러개일 수 있다.
// 1 base 로 작성

public class Main {
	
	public static void main(String[] args) throws Exception{
		int N = 0;		// 학생 수 초기화 (1번 ~ N번)
		int M = 0;		// 키를 비교한 횟수
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());	// 학생수 입력
		M = Integer.parseInt(st.nextToken());	// 키를 비교한 횟수 입력
		
		ArrayList<Integer>[] G = new ArrayList[N+1];	// 키를 비교한 자료를 그래프에 입력하기 위한 선언
		int[] indegree = new int[N+1];					// 학생 번호 기준으로 indgree 숫자 저장을 위한 배열
		boolean[] isVisited = new boolean[N+1];			// 비교 완료해서 출력한 경우 true 로 마킹
		Queue<Integer> queue = new LinkedList<Integer>();	// indegree 가 0 인 정점을 담기위한 큐		
		StringBuffer sb = new StringBuffer();			// 출력 결과를 담을 객체 선언
		
		for (int i=0 ; i <= N ; i++) {					// 그래프 배열 생성 
			G[i] = new ArrayList<Integer>();
			
		}

		// 입력값을 그래프에 저장
		for (int i=0; i<M ; i++) {
			int a, b;				// 비교한 학생 중 키가 작은 학생의 번호를 a, 큰 학생의 번호를 b 로 임시 저장
			
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			G[a].add(b);			// 그래프에 키작은 학생 -> 키큰 학생 순으로 입력
			indegree[b]++;			// 키큰 학생의 인입 카운트 1 증가
			
		}
		
//		System.out.println(Arrays.toString(indegree));
		// G 는 디버그 모드에서 값 확인

		// 시작점을 큐에 입력 (indegree 가 0 인 정점)
		for (int i=1 ; i<=N ; i++) {		// indegree 0 은 의미 없으므로 1부터 시작
			if (indegree[i] == 0) {
				queue.add(i);
			}
		}
		
		// 큐가 비어있지 않으면 반복적으로 탐색 시작
		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;
			
			sb.append(now);		// indegree 가 0 인 학생 번호를 출력 결과에 저장
			sb.append(" ");
			
			// 해당 번호의 학생과 키를 비교한 학생을 순서대로 탐색
			for (int i=0 ; i < G[now].size() ; i++) {
				int next = G[now].get(i);
				if ( isVisited[next] == false) {		// 비교한적이 없는 경우
					indegree[next]--;					// indegree 1 감소
					if (indegree[next] == 0) {			// indegree 가 0 이면 큐에 저장
						queue.add(next);
					}
				}
			}
		}
		
		System.out.println(sb);	// 결과 출력
		
	}
}

/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */