[BOJ 백준] 줄세우기(2252) Java

링크 : https://www.acmicpc.net/problem/2252

2252번: 줄세우기

 

문제 설명 : 

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

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

 

입력 : 

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

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

 

출력 : 

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

 

예제 입력 : 

3 2
1 3
2 3

 

예제 출력 : 

1 2 3

 

접근법 : 

1) 어떻게 풀 것인가?

모든 학생의 키 순서는 알 수가 없다.

일부 학생들의 키 순서를 통해 전체적인 키의 대소관계에 맞게 출력해야한다. (답이 여러개가 가능한 문제)

 

학생의 키를 공장의 공정으로 바꿔보자.

A, B공정이 끝나야 D 공정을 시작할 수 있고,

C 공정이 끝나야 E공정을 시작할 수 있고

D, E공정이 끝나야 최종 F공정을 시작할 수 있다고 했을때

 

A → B → D → C → E → F

B → A → D → C → E → F

C → E → B → A → D → F

 

등 답이 여러개가 나올 수 있다.

 

왜냐하면 이러한 노드, 간선의 관계에서는 절대적인 노드의 순서가 정해진게 아니라,

어쨋든 상대적인 순서만 지켜서 실행하면 되기 때문이다.

 

즉, 노드들의 상대적인 위상이 중요한 그래프에서 "위상정렬"을 사용한다.

위상정렬의 핵심은 indegree 배열을 만들어 자신을 향하는 화살표가 0개가 될때,

실행할 수 있다는 것이다.

 

그리고 순서가 중요한게 아니라 indegree가 0임을 만족하면 실행할 수 있기 때문에

BFS와 유사하게 선입선출 구조로 간선을 제거해나가면 된다.

따라서 Queue 자료구조를 사용하면 된다.

 

참고 : 위상정렬

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

 

2) 시간복잡도

모든 Node가 연결된 최악의 경우 시간복잡도는 O(N^2)인데 간선 수가 100,000 으로 주어져있으므로 

시간은 여유있음 (Java 기준 -  476ms)

 

3) 공간복잡도

가장 메모리를 많이 차지할 간선배열을 정적 int 배열로 한다면

int [32000][100000] = 4Bytes * 32,000 * 100,000 = 12,207 MB로 당연히 memory를 초과하게 된다.

따라서 Java의 경우 ArrayList를 통한 동적배열을 만들어줘야하고, C++의 경우 Vector를 통한 동적배열 필요.

 

이 경우 100,000개의 int 배열이므로 390Kbytes (4Bytes * 100,000 /1024) 단위로 아주 양호하다.

 

4) 풀면서 놓쳤던점

간선리스트에 edge[a].add(b) 를 해야하는데 (출발점에서 끊어줘야하므로)

edge[b].add(a) 를 해서 순간적으로 당황함.

 

5) 이 문제를 통해 얻어갈 것

기본적인 그래프에 대한 개념 (Node와 Edge)

지향성, 무지향성을 어떻게 처리할 것인가.

심화한다면 이 문제를 LIS로 어떻게 풀것인가?

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 줄세우기 백준 2252
public class Main {

	static int N, M, cnt;
	
	static int[] indegree;			// indegree 배열  ( 1 ~ N번 노드 각각 진입차수)
	static ArrayList[] edgeList; 	// 간선정보 배열 (queue에서 poll 할때 간선 잘라주는 용도이므로 출발지에 add함)
                                    // edgeList[ 3 ] = 3번에서 출발, 도착점을 ArrayList<Integer> 관리
	                                // edgeList[ 5 ] = 5번에서 출발, 도착점을 ArrayList<Integer> 관리

	static ArrayDeque<Integer> queue;	// 위상정렬용 Queue   (indegree가 0인 경우 queue에 추가)
	
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 0. 입력조건 초기화 
		// N 학생수 / M 간선수
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		sb = new StringBuilder();		// 정답 출력용 String
		indegree = new int[N + 1];		// indegree 배열 		
		
		// 간선배열 2차원 (동적 할당 가능) 으로 선언
		edgeList = new ArrayList[ N + 1 ];				
		for(int i=1; i<=N; i++) {
			edgeList[ i ] = new ArrayList<Integer>();
		}
		queue = new ArrayDeque<Integer>(); // Queue 선언
				
		// 1. 입력받으면서 작은 녀석에 간선배열을 넣고, 큰 녀석에 indegree를 추가시킴
		for(int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			int startId = Integer.parseInt(st.nextToken());
			int targetId = Integer.parseInt(st.nextToken());
			
			// 1) 출발지점에서 끊어줄 준비
			edgeList[startId].add(targetId);
			// 2) 도착지점 indegree +1
			indegree[targetId]++;
		}
		
		// 2. 초기화 - 최초 공정들 queue에 넣기
		for (int i = 1; i<=N; i++) {
			if (indegree[i] == 0)  queue.add(i);
		}
		
		// 3. 위상정렬
		while( ! queue.isEmpty()) {
			 // ** 현재 단계 clear
			int startId = queue.poll();
			sb.append(startId+" ");
			
			for (int i = 0; i < edgeList[startId].size(); i++) {
				int targetId = (int) edgeList[startId].get(i);
				
				// 1) 타겟에 내가 끝났음을 알림  (indegree [target] -- )
				indegree[targetId]--;
				
				// 2) 타겟의 indegree 가 0이면 enqueue
				if (indegree[targetId] == 0 ) {
					queue.add(targetId);
				}
			}
		}
		
		
		
		// 4. 출력
		bw.write(sb.toString());
		
		
		bw.flush();
		bw.close();
		br.close();
	}
}