문제 링크 : https://www.acmicpc.net/problem/2252
줄 세우기
문제
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.
입력
첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
출력
첫째 줄부터 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.
예제
3 2
1 3
2 3
출력 -> 1 2 3
4 2
4 2
3 1
출력 -> 4 2 3 1
접근하기
아주 전형적인 위상 정렬 문제이다.
코드
package boj;
import java.util.*;
public class boj_2252 {
static int N;
static int M;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
List<List<Integer>> list = new ArrayList<>(); //연관된 두 숫자가 들어 갈 수 있게 선언
int[] indegree = new int[N+1];
for(int i=0; i<N+1; i++) list.add(new ArrayList<Integer>());
for(int i=0; i<M; i++){
sc.nextLine();
int v1 = sc.nextInt();
int v2 = sc.nextInt();
list.get(v1).add(v2); //v1 숫자에 연결된 v2를 선언
indegree[v2]++; //v2 숫자엔 v1이 최소 하나 연결 되었으니 indegree를 추가 해준다.
}
sc.close();
polo(indegree, list);
}
public static void polo(int[] indegree, List<List<Integer>> list){
Queue<Integer> q = new LinkedList<>();
Queue<Integer> result = new LinkedList<>();
for(int i=1; i<=N; i++){
if(indegree[i]==0){
q.offer(i); //indegree가 0인 숫자 = 현 상태 가장 앞의 숫자를 q에 넣어준다.
}
}
while(!q.isEmpty()){
int node = q.poll(); //q에서 꺼내서 result로 넣어준다. 가장 앞의 숫자니까.
result.offer(node);
for(Integer linked : list.get(node)){
//현재 가장 앞 숫자인 node에 연결된 숫자들을 맨 앞으로 가져오기 위해 indegree를 --해서 0으로 맞춰주고 이를 가장 우선순위로 생각하여 q에 넣어준다.
indegree[linked]--;
q.offer(linked);
}
}
while(!result.isEmpty()){
System.out.print(result.poll()+" ");
}
}
}코드가 꽤 길지만 주석으로 중요부분을 설명해두었다.
가장 중요한 알고리즘 포인트는
public static void polo(int[] indegree, List<List<Integer>> list){
Queue<Integer> q = new LinkedList<>();
Queue<Integer> result = new LinkedList<>();
for(int i=1; i<=N; i++){
if(indegree[i]==0){
q.offer(i); //indegree가 0인 숫자 = 현 상태 가장 앞의 숫자를 q에 넣어준다.
}
}
while(!q.isEmpty()){
int node = q.poll(); //q에서 꺼내서 result로 넣어준다. 가장 앞의 숫자니까.
result.offer(node);
for(Integer linked : list.get(node)){
//현재 가장 앞 숫자인 node에 연결된 숫자들을 맨 앞으로 가져오기 위해 indegree를 --해서 0으로 맞춰주고 이를 가장 우선순위로 생각하여 q에 넣어준다.
indegree[linked]--;
q.offer(linked);
}
}
while(!result.isEmpty()){
System.out.print(result.poll()+" ");
}
}여기만 보면 된다.
위는 모두 초기화 과정이기에 보면 이해 될 것이다.
위의 중요 코드에서 가장 앞 숫자들로 구성하는 q를 보면 된다.
첫 번째 for문
for(int i=1; i<=N; i++){
if(indegree[i]==0){
q.offer(i); //indegree가 0인 숫자 = 현 상태 가장 앞의 숫자를 q에 넣어준다.
}
}여기서 N(노드 수) 만큼 반복문을 돌면서 indegree가 0인 숫자들만 q에 넣어준다.
이게 뭐냐? 즉, indegree==0인 가장 맨 앞의 숫자들을 q에 넣겠다는 거
그럼 q에 넣어서 무엇을 하는가?
while(!q.isEmpty()){
int node = q.poll(); //q에서 꺼내서 result로 넣어준다. 가장 앞의 숫자니까.
result.offer(node);
for(Integer linked : list.get(node)){
//현재 가장 앞 숫자인 node에 연결된 숫자들을 맨 앞으로 가져오기 위해 indegree를 --해서 0으로 맞춰주고 이를 가장 우선순위로 생각하여 q에 넣어준다.
indegree[linked]--;
q.offer(linked);
}
} q에서 poll()로 하나를 꺼낸다.
그걸 result에 넣고
꺼낸 node와 연결된 숫자들을 list에서 찾아서 걔네들의 indegree를 낮춰준다.
왜???
그래야 걔네들이 다음으로 맨 앞에 올 숫자들이 될테니!!
그럼 걔네들을 q에 넣어준다.
우린 지금 while문 안에 있고 조건은 q가 empty하기전까지 이다.
즉, q가 있는 한 while은 계속 돌게 되어있다!
그렇게 돌다보면 result에 다 들어가게 된다.
끝!
