패스트캠퍼스 챌린지 30일차

위상 정렬 (Topological Sort)

  - 정점들을 위상에 맞춰 정렬

 

 • DAG (Directed Acyclic Graph)

  Directed = 간선에 방향성이 있다 

  Acyclic : 싸이클이 없다

  Graph = 정점 + 간선

 

Indegree : 자신(정점) 에 들어오는 개수 (차수)

Outdegeree : 자신에서 나가는 간선의 개수(차수)

 

 

<키워드>

 제일 먼저 올 수 있는 정점은?

  => 들어오는 간선이 없는 정점

 

정리

 1. 정점들의 Indegree, Indeg[1...N] 계산하기

 2. 들어오는 간선이 0개인 (indeg[i] ==0) 정점들을 찾아서 자료구조 D에 넣기

 3. D가 빌 떄 까지

  1. D에서 원소 X를 꺼내서 정렬 시키기

  2. Graph 에서 정점 X 제거하기

  3. 새롭게 정렬 가능한 점을 찾아서 D에 넣기 => O(V + E)

 

줄 세우기 (BOJ 2252)

 - 학생들 간에 위상 관계가 주어지고, 이에 맞게 줄을 세운다 

 - 정점 V : i 번 학생이 i 번 정점

 - 간선 E : x 번 학생이 y번 학생보다 먼저 서야한다

    static int N, M;
    static int[] indeg;
    static ArrayList<Integer>[] adj;
    
    static void pro() {
        Deque<Integer> queue = new LinkedList<>();
        // 제일 앞에 "정렬될 수 있는" 정점 찾기
        for (int i = 1; i <= N; i++)
            if (indeg[i] == 0)
                queue.add(i);
            

        // 정렬될 수 있는 정점이 있다면?
        // 1. 정렬 결과에 추가하기
        // 2. 정점과 연결된 간선 제거하기
        // 3. 새롭게 "정렬 될 수 있는" 정점 Queue에 추가하기
        while (!queue.isEmpty()) {
            int x = queue.poll();
            sb.append(x).append(' ');
            for (int y : adj[x]) {
                indeg[y]--;
                if (indeg[y] == 0) queue.add(y);
            }
        }
        System.out.println(sb);
    }

 

 

ACM Craft (BOJ 1005)

	static int N, M;
	static int[] indeg, T_done, T;
	static ArrayList<Integer>[] adj;

	static void pro() {
        Deque<Integer> queue = new LinkedList<>();
        // 제일 앞에 "정렬될 수 있는" 정점 찾기
        for (int i = 1; i <= N; i++)
            if (indeg[i] == 0) {
                queue.add(i);
                T_done[i] = T[i];
            }

        // 위상 정렬 순서대로 T_done 계산을 함께 해주기
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int y : adj[x]) {
                indeg[y]--;
                if (indeg[y] == 0) queue.add(y);
                T_done[y] = Math.max(T_done[y], T_done[x] + T[y]);
            }
        }
        int W = scan.nextInt();
        System.out.println(T_done[W]);
    }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

30일차 인증

 

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]