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

🔗 2252번 : 줄 세우기
● Java 풀이
● 시간 제한 2초
● 메모리 제한 128 MB

 

문제

 

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

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

 

테스트 케이스

/** 출처 (https://www.acmicpc.net/board/view/130776) **/
// input
9 10
1 3
2 3
2 4
2 5
3 6
3 7
4 7
5 7
6 8
7 8

// answer
1 2 3 4 5 6 7 8 9 

// input 
4 4
1 3
3 2
1 2
1 4

// answer
1 3 2 4 

/** 출처 (https://www.acmicpc.net/board/view/74119) **/
// input 
5 4
2 3
1 2
4 2
5 2

// answer
1 4 5 2 3

 

풀이

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static int N, M;  // 학생 N명, 키 비교 횟수 M번
    private static StringBuilder sb;
    private static List<Integer>[] nodes;
    private static boolean[] visited;

    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());
        sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        nodes = new ArrayList[N + 1];  // 부모노드를 가리킬 리스트
        visited = new boolean[N + 1];  // 방문 처리

        int a, b;  // 학생들을 임의로 저장할 변수 선언

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            if (nodes[b] == null) nodes[b] = new ArrayList<>();
            nodes[b].add(a);  // 자식 노드에 부모 노드 연결 (작은 사람이 우선순위 높음)
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {  // 방문하지 않았을 경우
                dfs(i);  // 해당 경로로 거치는 모든 노드 DFS
                //System.out.println(" 방문");
            }
        }
        
        bw.append(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int n) {
        visited[n] = true;

        if (nodes[n] != null) {  // null일 경우 (루트노드일 경우) 바로 출력
            for (int parent : nodes[n]) {
                if (!visited[parent]) dfs(parent);  // 부모 노드로 이동하는 DFS 재귀
            }
        }

        sb.append(n).append(" ");  // 제일 작은 노드부터 삽입
        //System.out.print(n);
    }
}

 

위상 정렬 문제. 이렇게 하나 또 배워 간다.

처음엔 우선순위를 누적 합으로 매기는 방식으로 풀었는데, 시간 초과가 났다.

 

문제에서 주는 테스트 케이스에서 1 → 3, 2 → 3을 출력하려면, 무조건 리프 노드부터 시작해야 한다고 생각해서 그래프 방식으로 풀지 않았었는데, 결국 서로 연결고리가 없는 자식 노드들은 순서를 아무렇게나 해도 상관없다는 뜻이 된다는 게 위상 정렬 방식으로 풀고 나니 알겠다.