위상정렬(줄세우기, 최종순위)

• 위상정렬
  • 앞뒤 관계가 존재
  • DAG
    • 단방향 그래프
    • 사이클 x
  • 진입차수가 0인 지점이 존재해야한다
  • n번만큼 진행하면서
    • 도중에 큐가 빈다면 -> 사이클 존재 -> 위상정렬x
    • 큐에 2개 이상 들어있다면 -> 여러 답안이 존재
    • 큐에 1개씩 들어있다면 -> 하나의 답안 존재

 

 

[줄세우기 - 2252]

 

 

* 조건

• N명의 학생
• 모든 학생의 키를 비교하진 않고, 일부 학생의 키를 비교
• 비교한 뒤 나올 수 있는 여러답 중 하나를 출력

 

* 로직

• 인접 리스트(단방향) 생성
• 진입 차수에 대한 배열 관리 (numberOfEntry[])
• 위상정렬 진행
  • 진입 차수가 0인 노드를 큐에 담기
  • 큐를 꺼내고 인접한 노드들의 간선을 제거
  • 진입차수가 0인 노드 큐에 담기
  • N만큼 반복

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Problem_2252 {

    static int N;   //학생 수
    static int M;   //키를 비교한 횟수
    static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    static int[] numberOfEntry;     //진입 차수
    static ArrayList<Integer> answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String config = br.readLine();
        st = new StringTokenizer(config, " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0; i<=N; ++i){
            adjList.add(new ArrayList<>());
        }

        numberOfEntry = new int[N+1];
        for(int i=0; i<M; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adjList.get(v1).add(v2);
            numberOfEntry[v2]++;
        }

        topologicalSort();

        if(answer.size() == 0) System.out.println(0);
        else {
            for(int ans : answer)
                System.out.print(ans + " ");
        }
    }

    private static void topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        answer = new ArrayList<>();

        //진입차수가 0인 노드를 큐에 푸쉬
        for(int i=1; i<=N; ++i){
            if(numberOfEntry[i] == 0) queue.offer(i);
        }

        //pop -> pop된 노드에서의 연결을 제거
        for(int i=1; i<=N; ++i){
            if(queue.isEmpty()) {
                answer = new ArrayList<>();
                return;
            }
            int q = queue.poll();
            answer.add(q);

            for(int node : adjList.get(q)){
                numberOfEntry[node]--;

                //진입차수가 줄어들때 0이 되면 큐에 푸쉬
                if(numberOfEntry[node] == 0) queue.offer(node);
            }
        }
    }
}

 

 

[최종 순위 - 3665]

 

 

* 로직

• 주어진 작년 팀의 등수를 기반으로 인접행렬을 작성한다(단방향)
• 상대적인 등수가 바뀐 부분의 인접행렬과 진입차수를 변경한다
• 위상정렬을 진행한다
  • N팀만큼 진행하는 동안
    • 큐가 비어있다면 -> Impossible
    • 큐에 2개 이상 들어있다면 -> ?
    • 큐에 1개씩 들어있다면 -> 답 출력

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Problem_3665 {

    static int N;   //팀의 수
    static int M;   //상대적인 등수가 바뀐 횟수
    static int[] numberOfEntry;
    static int[][] adjMatrix;
    static ArrayList<Integer> originRank;
    static ArrayList<Integer> answer;
    static boolean check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int testCase = Integer.parseInt(br.readLine());
        int t=0;
        while (t < testCase){
            N = Integer.parseInt(br.readLine());
            numberOfEntry = new int[N+1];
            adjMatrix = new int[N+1][N+1];

            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            originRank = new ArrayList<>();
            while (st.hasMoreTokens()){
                originRank.add(Integer.parseInt(st.nextToken()));
            }

            for(int i=0; i<originRank.size(); ++i){
                int v1 = originRank.get(i);
                for(int j=i+1; j<originRank.size(); ++j){
                    int v2 = originRank.get(j);

                    adjMatrix[v1][v2] = 1;
                    numberOfEntry[v2]++;
                }
            }

            M = Integer.parseInt(br.readLine());
            for(int i=0; i<M; ++i){
                input = br.readLine();
                st = new StringTokenizer(input, " ");

                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                //서로 방향 바꿔주기
                if(adjMatrix[v1][v2] == 1){
                    adjMatrix[v1][v2] = 0;
                    adjMatrix[v2][v1] = 1;
                    numberOfEntry[v2]--;
                    numberOfEntry[v1]++;
                }
                else {
                    adjMatrix[v1][v2] = 1;
                    adjMatrix[v2][v1] = 0;
                    numberOfEntry[v2]++;
                    numberOfEntry[v1]--;
                }
            }

            check = true;
            topologySort();

            if(!check) System.out.println("?");
            else if(answer.size() == 0) System.out.println("IMPOSSIBLE");
            else {
                for(int ans : answer)
                    System.out.print(ans + " ");
                System.out.println();
            }

            t++;
        }
    }

    private static void topologySort() {
        Queue<Integer> queue = new LinkedList<>();
        answer = new ArrayList<>();

        for(int i=1; i<=N; ++i){
            if(numberOfEntry[i] == 0) queue.offer(i);
        }

        for(int i=1; i<=N; ++i){
            int size = queue.size();

            //정확한 순위가 나오려면 큐에는 한개씩 들어가 있어야 함
            if(size > 1) {
                check = false;
                return;
            }

            //위상정렬이 만족 안되기 때문에 impossible
            if(size == 0) {
                answer = new ArrayList<>();
                return;
            }

            int q = queue.poll();
            answer.add(q);
            for(int j=1; j<=N; ++j){
                if(adjMatrix[q][j] == 1){
                    numberOfEntry[j]--;

                    if(numberOfEntry[j] == 0){
                        queue.offer(j);
                    }
                }
            }
        }
    }
}

 

일부 선행과정들이 주어지고, 그래프, 순서의 출력 등을 요구한다면 위상정렬을 생각해낼 필요성을 느꼈다.