백준 2252 줄 세우기 (JAVA 자바)

문제 출처 - www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

문제 유형 : 위상 정렬

문제 접근: 처음엔 인접 행렬로 접근했는데 메모리 초과가 떴다. arraylist를 활용한 인접 리스트로 푸니 맞힐 수 있었다. 그래프 문제는 대부분 인접리스트로 푸는게 유리한 것 같다. 

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		List <Integer> adj[] = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			adj[i]= new ArrayList<>();
		}
		
		int indegree[] = new int[N + 1];
		
		for (int i = 0; i < M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			adj[from].add(to);
			indegree[to]++;
		}
		
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			if(indegree[i] == 0) {
				q.offer(i);
			}
		}
		StringBuilder sb = new StringBuilder();
		while(!q.isEmpty()) {
			int cur = q.poll();
			sb.append(cur).append(" ");
			for (int i = 0; i < adj[cur].size(); i++) {
				if(--indegree[adj[cur].get(i)] == 0) {
						q.offer(adj[cur].get(i));
					}
				}
			}
		System.out.println(sb);
	}
}