문제
인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.
그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.
- 1 4 3
- 6 2 5 4
- 2 3
첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정했다.
남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다. 남일이는 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다. 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다. 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.
경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다. 이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다. 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.
보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램을 작성하시오.
입력
첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다.
출력
출력은 N 개의 줄로 이뤄지며, 한 줄에 하나의 번호를 출력한 다. 이들은 남일이가 정한 가수들의 출연 순서를 나타낸다. 답이 여럿일 경우에는 아무거나 하나를 출력 한다. 만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다.
예제 입력 1
6 3
3 1 4 3
4 6 2 5 4
2 2 3예제 출력 1
6
2
1
5
4
3문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ2623 {
static int[][] graph;
static int N,M;
static int[] level;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
graph=new int[N+1][N+1];
level=new int[N+1];
for(int i=0;i<M;i++){
st=new StringTokenizer(br.readLine());
int num=Integer.parseInt(st.nextToken());
int[] tmp=new int[num];
for(int j=0;j<num;j++){
tmp[j]=Integer.parseInt(st.nextToken());
}
for(int j=0;j<num-1;j++){
if(graph[tmp[j]][tmp[j+1]]!=1) {
graph[tmp[j]][tmp[j + 1]] = 1;
level[tmp[j + 1]] += 1;
}
}
}
bfs();
}
private static void bfs() {
Queue<Integer> queue=new ArrayDeque<>();
ArrayList<Integer> list=new ArrayList<>();
for(int i=1;i<=N;i++){
if(level[i]==0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
int q=queue.poll();
list.add(q);
for(int i=1;i<=N;i++){
if(graph[q][i]==1){
level[i]-=1;
if(level[i]==0) {
queue.offer(i);
}
}
}
}
if(list.size()==N){
for(int i=0;i<N;i++){
System.out.println(list.get(i));
}
}else{
System.out.println(0);
}
}
}M 개의 숫자 정렬을 모두 만족하도록 순서를 정하는 문제이다.
이 문제를 풀기 위해선 위상정렬이라는 알고리즘을 이용해야한다.
위상정렬이란?
정렬 알고리즘으로 여러 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것이다.
예를 들어 아래와 같은 예시가 있다고 했을 때
A 라는 과목을 들은 후에야 B, C, D 과목 수업을 들을 수 있고, C 과목을 들은 후에야 E 과목을 들을 수 있다. 이때 어떤 순서대로 수업을 들어야 모든 수업을 들을 수 있는지 정하는 것이 위상정렬이다.
즉, 그래프 정렬이라고 생각하면 되는데 주의해야할 점은 사이클이 있어선 안되고 방향 그래프라는 것이다.
위상정렬 알고리즘을 만들기 위해서는 진입차수 라는 개념을 이용한다. 진입차수란 한 정점으로 들어오는 간선의 개수를 나타낸다. 위의 예시에서는 A는 0개, C는 1개가 되는 것이다.
위상정렬 알고리즘
- 진입차수가 0인 정점과 이와 연결된 간선을 모두 지운다.
- 남아있는 정점들의 진입차수를 갱신한다. -> 지워진 정점과 연결된 정점들의 진입차수를 각각 -1 한다.
- 모든 정점을 출력할때까지 반복한다.
위의 예시를 들어보면 현재 A 정점만 진입차수가 0이기 때문에 A 정점과 연결된 간선들을 모두 지운다.
첫 1,2번을 수행한 결과이다. B, C, D 정점의 진입차수를 0으로 갱신하고 다시 1,2번을 반복하면 C 정점과 연결된 E 정점만 남게 된다.
즉, 출력의 순서가 A -> B -> C -> D -> E 가 된다. (물론 B,C,D의 순서는 바뀔 수 있다.)
위상정렬 코드
// graph : 간선의 정보가 들어간 이차원 배열
// level : 진입차수의 정보가 들어간 일차원 배열
Queue<Integer> queue=new ArrayDeque<>();
ArrayList<Integer> list=new ArrayList<>();
for(int i=1;i<=N;i++){
if(level[i]==0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
int q=queue.poll();
list.add(q);
for(int i=1;i<=N;i++){
if(graph[q][i]==1){
level[i]-=1;
if(level[i]==0) {
queue.offer(i);
}
}
}
}
System.out.println(list);위상정렬 알고리즘을 이용하여 문제를 풀어보자.
간선 정보와 진입차수 정보 알아내기
graph=new int[N+1][N+1];
level=new int[N+1];
for(int i=0;i<M;i++){
st=new StringTokenizer(br.readLine());
int num=Integer.parseInt(st.nextToken());
int[] tmp=new int[num];
for(int j=0;j<num;j++){
tmp[j]=Integer.parseInt(st.nextToken());
}
for(int j=0;j<num-1;j++){
if(graph[tmp[j]][tmp[j+1]]!=1) {
graph[tmp[j]][tmp[j + 1]] = 1;
level[tmp[j + 1]] += 1;
}
}
}graph는 간선의 정보를 level에는 진입차수 정보를 넣어준다. 각 PD가 뽑은 순서대로 간선의 정보와 진입차수 정보를 알아내야 하기 때문에 tmp라는 임시 배열을 만들어 순서를 넣어주고 간선의 정보를 채워준다.
예를 들면, 1 4 3 의 순서가 들어오면 tmp 배열에 순서대로 넣어주고 다시 반복문을 돌려 graph[1][4], graph[4][3] 에 값을 채워주는 것이다.
이때 진입차수의 개수도 함께 갱신해준다.
주의해야할 점은 다른 PD가 정한 순서가 겹치는 경우이다.
1 2
1 2두 PD가 정한 순서가 위와 같다면 2의 진입차수는 2가 아니라 1이기 때문에 if문을 통해 이미 간선의 정보가 있다면 진입차수를 갱신하지 않도록 처리한다.
위상정렬
Queue<Integer> queue=new ArrayDeque<>();
ArrayList<Integer> list=new ArrayList<>();
for(int i=1;i<=N;i++){
if(level[i]==0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
int q=queue.poll();
list.add(q);
for(int i=1;i<=N;i++){
if(graph[q][i]==1){
level[i]-=1;
if(level[i]==0) {
queue.offer(i);
}
}
}
}진입차수가 0인 정점들을 모두 queue에 넣어주고 정렬을 시작한다.
queue에서 뽑아낸 값들은 list에 넣어주어 사이클이 있는지 판단한다.
뽑아낸 정점과 연결되어있는 정점들의 진입차수를 하나씩 줄여주고 그 중 진입차수가 0인 정점들만 queue에 넣어주어 다음 정점들을 탐색한다.
이 과정을 모두 반복하면 list에 정점들이 순서대로 들어가게 된다.
사이클 유무 판단
if(list.size()==N){
for(int i=0;i<N;i++){
System.out.println(list.get(i));
}
}else{
System.out.println(0);
}list에 모든 정점들이 다 들어가면 사이클이 없는 것이기 때문에 정점들을 순서대로 출력해주고
list의 크기가 N이 아니라면 사이클이 발생한 것이므로 0을 출력해준다.
위상정렬 알고리즘을 공부하면서 코드를 짰는데 18%에서 틀렸다고 떠서 오류를 찾느라 시간이 꽤 걸렸다.
다른 PD가 똑같은 순서를 짰을때를 예외처리 해주지 않아서 틀렸다고 떴다. 다 되었다고 생각할때마다 하나씩 빠지는 부분들이 있어서 꼼꼼히 코드를 짜야할 것 같다.
참고 위상정렬 알고리즘
