[백준] 알고리즘 분류(그래프 이론,JAVA)2623번, 음악프로그램

문제 링크

2623번: 음악프로그램

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 각 보조 PD마다 출연 가수의 순서를 가지고 있다.

2. 보조 PD 순서를 모두 만족하는 전체 가수의 순서를 결과로 출력합니다.

3. 답이 여럿일 경우 아무거나 하나를 출력이 가능하며, 불가능할 경우 0을 출력한다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 위상 정렬을 통해서 가수가 출연하는 순서를 탐색합니다.

 

3. 탐색이 종료되었을 때 가수가 출연하는 순서를 결과로 출력합니다.

 

각 지역 최단 거리 탐색!

 

 

위상 정렬을 통해서 모든 보조 PD의 순서에 만족하는 전체 순서를 구합니다.

위상정렬 - 위키백과, 우리 모두의 백과사전

 

 

예를 들어 아래와 같은 상황일 때

	2	3	5	7	8	9	10	11
child	1	0	0	0	2	2	2	2

 

child가 0일 때 가수 출연 가능!

 

Why?

 

해당 가수보다 순서가 앞에 오는 가수들이 모두 공연을 진행했다고 판단할 수 있기 때문입니다.

 

{3, 5, 7} 가수 출연!

 

	2	3	5	7	8	9	10	11
child	1	0	0	0	0	2	0	2

 

{8, 9} 가수 출연!

 

 

....

 

이러한 방식으로 가수들을 출연시켜서 전체 가수가 출연되었을 때 전체 순서를 구하면 됩니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 6

M : 3

 

가수 출연 관계 정보

 

 

	1	2	3	4	5	6
child	0	1	2	2	1	0

 

2. 위상 정렬을 통해서 가수가 출연하는 순서를 탐색합니다.

 

위상 정렬을 이용한 탐색 진행!

child 0 : { 1, 6 } 

가수 출연 순서 : 1 ▶ 6

 

	1	2	3	4	5	6
child	0	0	2	1	1	0

 

 

child 0 : { 2 } 

가수 출연 순서 : 1 ▶ 6 ▶ 2

	1	2	3	4	5	6
child	0	0	1	1	0	0

 

child 0 : { 5 } 

가수 출연 순서 : 1 ▶ 6 ▶ 2 ▶ 5

	1	2	3	4	5	6
child	0	0	1	0	0	0

 

child 0 : { 4 } 

가수 출연 순서 : 1 ▶ 6 ▶ 2 ▶ 5 ▶ 4

	1	2	3	4	5	6
child	0	0	0	0	0	0

 

child 0 : { 3 } 

가수 출연 순서 : 1 ▶ 6 ▶ 2 ▶ 5 ▶ 4 ▶ 3

 

모든 가수 출연 완료!

 

3. 탐색이 종료되었을 때 가수가 출연하는 순서를 결과로 출력합니다.

 

 

조건에 만족하는 가수들 출연 순서 :  1 ▶ 6 ▶ 2 ▶ 5 ▶ 4 ▶ 3

1 6 2 5 4 3 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 보조PD들이 가져온 가수 순서들을 띄어쓰기 기준 나누었습니다.
• 위상 정렬을 이용하여 각 가수들의 출연 순서를 구합니다.
• 탐색이 종료되었을 때 전체적인 가수 출연순서를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    //HashSet을 사용한 이유는 중복되는 값이 들어갈 수도 있기 때문입니다.
    //자신 바로 앞 출연 가수를 저정하는 리스트
    static ArrayList<HashSet<Integer>> list = new ArrayList<>();
    static int[] count;		//바로 앞 가수의 개수 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        StringBuilder answer = new StringBuilder();
        count = new int[N+1];
        for(int i=0;i<=N;i++)
        	list.add(new HashSet<>());
        //M명의 보조 PD에 대한 출연 순서 저장!
        for(int i=0;i<M;i++) {
        	st = new StringTokenizer(br.readLine()," ");
        	int size = Integer.parseInt(st.nextToken());
        	if(size == 0)	//순서가 없을 때
        		continue;
        	int pre = Integer.parseInt(st.nextToken());	//바로 앞 출연 가수
        	//바로 앞 출연가수 기준 저장
           	for(int j=1;j<size;j++) {
        		int cur = Integer.parseInt(st.nextToken());
        		if(!list.get(pre).contains(cur)) {
        			list.get(pre).add(cur);
        			count[cur]++;
        		}
        		pre = cur;	//바로 앞 출연가수 변경
        	}
        }
        //출연한 순서 저장하는 Queue
        Queue<Integer> result = new LinkedList<>();
        //위상 정렬에 사용할 Queue
        Queue<Integer> q = new LinkedList<>();
        //앞에 와야할 가수가 없는 가수들 Queue 저장
        for(int i=1;i<=N;i++)
        	if(count[i] == 0)
        		q.offer(i);
        //위상 정렬 탐색 진행!
        while(!q.isEmpty()) {
        	int cur = q.poll();
        	result.offer(cur);
        	for(int nxt : list.get(cur)) {
        		count[nxt]--;
        		if(count[nxt] == 0) 	//더 이상 앞에 와야할 가수가 없을 때
        			q.offer(nxt);
        	}
        }
        //모든 가수가 출연순서에 맞게 나올 때
        if(result.size() == N) {
        	//출연 순서에 맞게 BufferedWriter 저장
            while(!result.isEmpty()) {
        		bw.write(String.valueOf(result.poll()));
        		bw.newLine();
        	}
        }else 	//모든 가수가 출연순서에 맞게 나오지 못할 때
        	bw.write("0");	//BufferedWriter 0 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}