[BOJ] 백준 2623 음악프로그램

출처: https://www.acmicpc.net/problem/2623

 Input 

6 3

3 1 4 3

4 6 2 5 4

2 2 3

 

 Output 

6
2
1
5
4
3

정점별 선후관계

DFS를 활용한 위상정렬 (Topological sort) 이용

* 그래프가 사이클을 형성하여 위상정렬 되지 않는지 확인 필요.

위상정렬 (Topological sort)

 

구현

① 그래프 표현(인접리스트, 인접행렬)

→ 인접리스트

② 위상정렬 구현 (진입indegree차수, DFS)

     → DFS

③ 사이클 형성 유무 확인

④ 위상정렬 결과 중 다른 제약이 있는지.

    ex) 많은 위상정렬 결과를 모두 인정하는지 등

 

시뮬레이션

 

▶ 낮은 번호 정점 [1] → [4] DFS

visited = [T F F T F F]

finished =[F F F F F F] 

stack = [ ]

 

 

▶ 정점 [4] → [3] 

; DFS 순회 종료 후 방문한 정점 stack push & visited[] 초기화

visited = [T F T T F F]

finished =[T F T T F F] 

stack = [3, 4, 1]

 

 

방문하지 않은 정점 중 낮은 번호 정점 [2] 순회

▶ [2] → [3] 

    정점 [3]은 이미 finished이므로 stack push X

    대신, 정점 [2]는 정점 [5] 방문

visited = [F T T F F F]

finished = [T F T T F F] 

stack = [3, 4, 1]

 

▶ [2] → [5]

    visited = [F T F F T F]

    finished =[T F T T F F] 

    stack = [3, 4, 1]

▶ [5] → [4] ; DFS 종료

    아직 finshed 되지 않은 정점 [5], [2]를 stack에 push하고 visited[] 초기화

visited = [F T F T T F]

finished =[T T T T T F] 

stack = [3, 4, 1, 5, 2]

 

▶ [6] → [2] ; DFS 종료

    finished 되지 않은 정점 중 낮은 번호 정점 [6] 순회

    정점 [6]을 제외하고는 모두 finished[] = true 이므로, 정점 [6] stack에 push하고 visited[] 초기화

visited = [F T F F F T]

finished =[T T T T T T] 

stack = [3, 4, 1, 5, 2,  6]

 

stack의 원소를 역순으로 출력하면 위상정렬 순서!

▶ 6 2 5 1 4 3 

※ 위 경우에는 낮은 번호를 우선해서 탐색하였기에

    특정 기준에 따라 다른 위상정렬 경로가 나올 수 있음

 

사이클 유무 확인

▶ 정점 [1] → [6] → [5]  → [2] 

visited = [T T F F T T]

 

▶ 정점 [2] → [1]

visited = [T T F F T T]

DFS 과정에서 이미 방문한 정점 [1]을 재방문하여 사이클 확인!

---

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static boolean[] finished, visited;
    static Stack<Integer> stack;
    static int answer;
    static ArrayList<ArrayList<Integer>> adList;
    static final int SUCCESS = 1;
    static final int IMPOSSIBLE = 2;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 정점의 개수
        int N = Integer.parseInt(sc.next());
        
        // 인접 리스트로 구현
        adList = new ArrayList<>();
        adList.add(new ArrayList<>());
        for(int i=1; i<=N; i++) adList.add(new ArrayList<>());
        
        // 보조 PD의 수
        int M = Integer.parseInt(sc.next());
        
        for(int i=1; i<=M; i++) {
            int singerCnt = Integer.parseInt(sc.next());
            
            // 맡은 출연 가수가 0개이거나 1개이면 의미가 없다.
            if(singerCnt <= 1 ) continue;
            
            // 우선 제일 처음 할 가수를 입력 받는다.
            int vertex = Integer.parseInt(sc.next());
            int afterVertex;
            // 주어진 개수에 맞게 마지막 간선 연결을 제외하고 간선을 잇는다.
            for(int j=1; j<=singerCnt-2; j++) {
                afterVertex = Integer.parseInt(sc.next());
                adList.get(vertex).add(afterVertex);
                vertex = afterVertex;
            }
            // 마지막 간선을 잇는다.
            afterVertex = Integer.parseInt(sc.next());
            adList.get(vertex).add(afterVertex);
        }
        
        visited = new boolean[N+1];
        finished = new boolean[N+1];
        stack = new Stack<>();
        
        answer = SUCCESS;
        for(int i=1; i<=N; i++) {
            // 위상정렬 완료된 정점이라면 pass
            if(finished[i]) continue;
            // 아직 완료되지 않은 정점이라면 DFS를 통해 탐색
            DFS(i);
            if(answer == IMPOSSIBLE) {
                System.out.println("0");
                return;
            }
        }
        // 정답 출력
        while(!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    private static void DFS(int v) {
        // 이번 DFS에서 이미 방문한 곳이면 사이클이 형성된 것
        if(visited[v]) {
            answer = IMPOSSIBLE;
            return;
        }
        // DFS 탐색 도중 이미 위상정렬 배치가 완료된 정점이라면 pass
        if(finished[v]) return;
        
        // 현재 방문한 곳 표시
        visited[v] = true;
        
        // 현재 정점과 연결된 모든 간선에 대하여 DFS를 하여야 한다.
        while(!adList.get(v).isEmpty()) {
            int next_v = adList.get(v).remove(0);
            DFS(next_v);
        }
        // 더이상 DFS할 연결된 정점이 없다면 스택에 넣어준다.
        stack.push(v);
        finished[v] = true;
        // 다음 DFS할 때 사이클 여부를 확인하기 위해 visited를 초기화 시켜둔다.
        visited[v] = false;
    }
}