[백준]2252번 줄세우기

2252번: 줄 세우기

문제 이해하기

• N명의 학생들을 “키 순서대로” 줄을 세울 것. 그런데 “키를 직접 재는 것이 아님”
  • 두 학생의 키를 “비교” 하여 줄을 세울 것.
  • 심지어 “일부 학생들의 키만” 비교 해 봄.
• 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램 작성하기

일부만 주어졌다는 것은 , 주어진 일부 외의 학생들은 “그 순서가 어떻게 되던 상관없다” 는 것으로 이해할 수 있을 듯 하다 → 따라서 정답은 여러가지가 될 수 있다.

• 문제에서도 “출력”에 [ 답이 여러가지인 경우 아무거나 출력한다 ] 라고 되어있다.
• 주어지는 문제의 조건
  • A B —→ A가 학생 B의 앞에 서야 한다.

문제 풀이

(:40)
어떤 순서를 만들어야 하는데, “조건”이 주어진다.

조건이 몇개 주어지며 조건을 만족하는 정답은 여러개가 나올 수 있다.

이 문제는 위상정렬 문제다

• 위상정렬로 풀이할 경우 , N(32000)+M(간선의개수==조건의개수==10만) 으로 풀 수 있다.

• 아직은 위상정렬을 바로 구현하는 부분에 있어 느리다는 것을 알 수 있었다.

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

public class Main {

  public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  public static int parseInt(String target){ return Integer.parseInt(target);}
  public static StringTokenizer st;
  public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static int n; // 학생 수

  public static List<Integer>[] preCondition = new List[32001];
  public static int[] ans; // 정답인 순서
  public static int[] cnt; // 각 노드의 진입차수

  public static void setting() throws IOException {
    st = new StringTokenizer(br.readLine());
    int m = 0; // 조건의 개수
    int a=0,b=0; // a 는 b 의 조건
    // n 과 m  : n 은 학생 수, m 은 조건의 개수
    n = parseInt(st.nextToken());
    m = parseInt(st.nextToken());

    // Init
    ans = new int[n];
    cnt = new int[n+1];

    // Init preCondition
    for (int i=1; i <= n;i++){
      // i 를 조건으로 갖는 노드들의 List 를 초기화
      preCondition[i] = new ArrayList<>();
    }
    // 각 조건의 형태 : A B --> A 는 B의 앞에 있어야 한다는 조건 --> A 는 B의 조건이다
    for (int i =0;i<m;i++){
      st = new StringTokenizer(br.readLine());
      a = parseInt(st.nextToken());
      b = parseInt(st.nextToken());
      preCondition[a].add(b); // a 를 조건으로 갖는 노드를 추가
      cnt[b]++; // b 의 진입차수를 1 증가
    }
  }
  public static void solve(){
    LinkedList<Integer> q = new LinkedList<>();
    // 진입 차수가 0인 노드들을 큐에 넣고 시작한다
    for ( int i =1; i <= n; i++){
      if (cnt[i]==0) q.add(i);
    }
    // q 에서 n 개의 노드를 뽑아 낼 수 있어야 한다.
    int cur = -1,order = 0;
    for (int i =0; i<n;i++){
      cur = q.poll();
      ans[order++] = cur;
      // 이 노드를 조건으로 갖는 노드들의 진입 차수를 1감소
      for (Integer adj : preCondition[cur]) {
        cnt[adj]--;
        // 감소시킨 후 진입차수가 0이 된 노드를 q 에 삽입
        if (cnt[adj] ==0) q.add(adj);
      }
    }
  }
  public static void printOrder() throws IOException{
    for(int i =0;i<n;i++){
      bw.write(ans[i]+" ");
    }
    bw.flush();
    bw.close();
  }

  public static void main(String[] args)throws IOException {
    setting();
    solve();
    printOrder();
  }
}