[문제풀이] 백준 2252 줄세우기

dfs를 이용한 위상정렬로 풀었습니다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Iterator; import java.util.Stack; public class 줄세우기_2252 { static int N; static int M; static ArrayList<Integer>[] arrayList; static int[] visit; static Stack<Integer> stack = new Stack<Integer>(); public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] tmp=br.readLine().split(" "); N=Integer.valueOf(tmp[0]); M=Integer.valueOf(tmp[1]); arrayList = new ArrayList[N+1]; visit=new int[N+1]; for(int i=1;i<=N;i++){ arrayList[i]=new ArrayList<Integer>(); } for(int i=0;i<M;i++){ tmp=br.readLine().split(" "); int a=Integer.valueOf(tmp[0]); int b=Integer.valueOf(tmp[1]); arrayList[a].add(b); } for(int i=1;i<=N;i++){ if(visit[i]==0) dfs(i); } //스택에 들어간 반대 순서대로 출력 while(!stack.isEmpty()){ System.out.print(stack.peek()+" "); stack.pop(); } } static void dfs(int x){ visit[x]=1; //arrayList[x]에 연결된 정점이고, 방문안한 정점이면 dfs로 방문 for(int i=0;i<arrayList[x].size();i++){ int next=arrayList[x].get(i); if(visit[next]==0) dfs(next); } //for문을 모두 끝냈으면 stack에 정점을 넣음 //즉, dfs로 방문한 정점이 역순으로 stack에 들어가게 된다. stack.push(x); } }