[BOJ] 백준 2252 줄세우기-java

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

 

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

 

학생들의 번호는 1번부터 N번이다.

 

 

출력

첫째 줄부터 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

 

문제:https://www.acmicpc.net/problem/2252

 

 

풀이

이 문제는 학생들의 키 순서를 전체적으로는 알 수 없고 부분적인 정보만을 제공합니다. 

그렇기 때문에 답은 여러 가지가 나올 수도 있습니다. 

일단 확실한 것은 두명의 학생의 키를 비교한 정보들만 알 수 있으므로 만약 어떤 학생은 다른 학생보다 작다는 정보를 받지 않았으면 그 학생은 제일 앞에 서도 된다는 뜻입니다. 

두 번째 줄부터 m+1번째 줄까지 받은 정보 중에 예 씨로 나온 1 3이라는 입력이 들어오면 1이라는 학생은 3이라는 학생보다 앞에서야 한다는 뜻인데 반대로 3이라는 학생은 1이라는 학생의 뒤에 서야 하기 때문에 (바로 뒤가 아니어도 뒤에 서면 됩니다.)  1이라는 학생이 먼저 앞에 서야 줄을 설 수 있습니다. 

그러한 점을 이용하여 a라는 학생의 뒤에 서야 하는 학생을 인접리스트로 나타냈습니다. 

graph라는 리스트의 a번째에는 인접리스트가 연결되어 있는데 그 인접 리스트엔 a번째 학생의 뒤에 서야 하는 학생들의 정보를 넣어놓습니다. 

그리고 degree라는 배열은 a라는 학생의 앞에 몇명의 학생이 있어야 하는지를 나타내는데 a라는 학생이 b,c라는 학생 뒤에 서야 한다는 입력을 받았다면 b와 c라는 학생이 줄을 서면 그때 degree를 하나씩 감소하여 2였던 degree[a]가 두 번 1씩 감소하여 0이 됩니다. 

그렇게 되면 a라는 학생은 줄을 서도 되는것이기때문에 그런 식으로 degree배열의 값으로 앞에부터 줄을 세워도 되는지 확인합니다. 

degree가 0인 학생부터 차례대로 queue에 추가한 뒤 그 학생의 degree는 -1로 바꿔주어 이미 줄을 섰다고 표시해줍니다.

 또한 a라는 학생이 큐에 들어간 순간(줄을 서면) a라는 학생보다 뒤에 서야 하는 학생들은 자신의 앞에 서야 하는 학생 한 명이 줄을 섰기 때문에 degree의 값을 1씩 줄여줘야 하고 줄인 값이 0이면 그 학생의 번호도 큐에 추가하면서 큐가 빌 때까지 반복합니다. 

큐가 비었다는 것은 모든 학생의 degree가 0이되어 큐에 들어가고 출력했다는 뜻으로 프로그램이 종료됩니다.