🔍 문제

📌 입력

📌 출력

💻 제출

🤔 문제 해결까지의 생각

입력 예제

2
goredrinker galeforce
riftmaker everfrost

각 아이템의 순서가 일부만 정해져 있으므로 전체의 순서를 한번에 알 수는 없다.

일부만 순서가 주어지는 경우에는 위상 정렬 풀이를 제일 먼저 생각할 수 있다.

해당 예제 값의 prev item 과 next item을 연결 하면 위와 같은 이미지 처럼 연결 되며 indegree는 해당 아이템을 사기 위한 이전 템들의 개수 이다.

indegree 값이 0인 item들은 먼저 제작해야 할 item이 존재 하지 않으므로 큐에 삽입이 된다.

데이터를 삽입하기 전에는 사전 순으로 데이터를 정렬해야 하고 정렬 된 데이터들은 큐에 삽입한다.

삽입된 큐의 데이터들은 위상정렬 로직을 거치면서 차수를 줄여가면 사전 순으로 출력이 될 것 이라고 생각 했다.

📝 제출 코드

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


public class Main {
    static int N;
    static Map<String, ArrayList<String>> relation = new HashMap<>();
    static Map<String, Integer> inDegree = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        N = Integer.parseInt(br.readLine()); //아이템 수

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");

            String prev = stD.nextToken();
            String next = stD.nextToken();

            if (relation.get(prev) == null) {
                relation.put(prev, new ArrayList<>());
                inDegree.put(prev, 0);
            }

            if (inDegree.get(next) == null) {
                relation.put(next, new ArrayList<>());
                inDegree.put(next, 0);
            }

            relation.get(prev).add(next);
            inDegree.put(next, inDegree.get(next) + 1);
        }

        solution();

        boolean flag = true;
        for (String key : inDegree.keySet()){
            if (inDegree.get(key) != 0){
                flag = false;
                break;
            }
        }

        bw.write(flag == true ? sb.toString() + " " : "-1\n");
        bw.flush();
        bw.close();
    }

    static void solution() {
        Queue<String> q = new LinkedList<>();

        ArrayList<String> inDegreeZero = new ArrayList<>();

        for (String key : inDegree.keySet()) {
            if (inDegree.get(key) == 0) { //차수가 0
                inDegreeZero.add(key);
            }
        }

        Collections.sort(inDegreeZero); //사전 정렬

        for (String key : inDegreeZero){ //사전 정렬 된 단어 삽입
            q.offer(key);
        }

        while (!q.isEmpty()){
            int size = q.size();

            ArrayList<String> sortStr = new ArrayList<>();
            for (int i=0; i<size; i++){
                String now = q.poll();
                sb.append(now + "\n");

                for (String next : relation.get(now)){
                    inDegree.put(next , inDegree.get(next) - 1); //차수 감소

                    if (inDegree.get(next) == 0){
                        sortStr.add(next);
                    }
                }
            }

            Collections.sort(sortStr);

            for (String data : sortStr){
                q.offer(data);
            }
        }
    }
}