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

solved.ac = 골드 2

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

2623번: 음악프로그램

 

---

1. 접근

문제 속 입력을 그래프로 만들어 위상 정렬하는 문제입니다.

 

처음에는 input으로 어떻게 그래프를 만들어야 하나 고민이 많았던 문젠데 예제 입력을 그림으로 그려보니 바로 이해가 되서 풀었던 문제입니다.

 

예제 입력의 두 번째 줄부터 간선 정보라 생각하고 그래프로 그려보면 다음과 같습니다.

 

입력 받은대로 단방향 그래프를 그리고 자신에게 향하는 간선이 없는 노드를 차례대로 삽입하면 문제의 정답을 구할 수 있습니다.

 

단, 위상 정렬은 사이클이 발생하지 않는 DAG 형태이어야 하는데 문제를 보면 예외 상황도 주어집니다.

따라서 정답 리스트를 삽입 후 출력하기 전에 노드 수 만큼 삽입이 되었는지 확인 후 출력해야 합니다.

 

---

2. 풀이

 

변수 세팅

static int N, M;
static int[] indeg;
static ArrayList<Integer>[] graph;
static ArrayList<Integer> answer = new ArrayList<>();
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    indeg = new int[N + 1];

    graph = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();
    for (int i = 1; i <= M; i++) {
        st = new StringTokenizer(br.readLine());
        int cnt = Integer.parseInt(st.nextToken()), x = Integer.parseInt(st.nextToken());

        // 간선 정보가 따로따로 입력된게 아닌 한 줄로 쭉 나와있으니
        // x를 바꿔가며 그래프를 생성한다.
        for (int j = 1; j < cnt; j++) {
            int y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            indeg[y]++; // y로 가는 간선 개수 추가
            x = y;
        }
    }

    solution();
}

 

탐색 및 정답 출력

static void solution() {
    Deque<Integer> queue = new LinkedList<>();
    // 들어오는 간선이 없는 노드를 추가한다.
    for (int i = 1; i <= N; i++) {
        if (indeg[i] == 0) queue.add(i);
    }

    while(!queue.isEmpty()) {
        int x = queue.poll();
        answer.add(x);
        for (int y : graph[x]) {
            indeg[y]--; // 방문했으니 들어가는 간선이 하나 줄어든다.
            if (indeg[y] == 0) queue.add(y);
        }
    }

    // 사이즈가 N개가 아니다 == 모든 가수의 순서를 정하지 못했다!
    if(answer.size() != N) System.out.println(0);
    else {
        for (int x : answer) sb.append(x).append('\n');
        System.out.println(sb.toString());
    }
}

 

---

3. 전체 코드