[BOJ] 백준 2252번 줄 세우기 (Java)

#2252 줄 세우기

난이도 : 골드 2

유형 : 그래프 이론/ 위상 정렬

2252번: 줄 세우기

▸ 문제

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

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

▸ 입력

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

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

▸ 출력

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

 

 

 

문제 풀이 🖋 

각 학생들의 키 순위를 메겨서 그대로 출력하면 되는 문제이다. 조건이 그렇게 까다롭지 않아 읽자마자 풀이 방식이 여러가지 생각났다.

 

---

처음으로 생각난 방식은 Map을 사용하여 Value값에 순위를 메겨 Value를 기준으로 Key를 정렬하여 그대로 Key를 출력하는 방식이었다.

 

그런데 틀렸다!

 

😅 틀린 코드 보기 ↓

Map<Integer, Integer> map = new HashMap<>();

for(int i=0; i<m; i++) {
	st=  new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	
	map.put(a, map.getOrDefault(a,0));
	map.put(b, map.getOrDefault(b,0)+1);
}

for(int rank : map.values()) {
	System.out.println(rank);
	
}

List<Entry<Integer, Integer>> list_entries = new ArrayList<>(map.entrySet());

Collections.sort(list_entries, new Comparator<Entry<Integer, Integer>>() {
	public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2)
	{
		return obj1.getValue().compareTo(obj2.getValue());
	}
});

for(Entry<Integer, Integer> entry : list_entries) {
	System.out.print(entry.getKey() + " ");
}

 

이유는 a와 b의 관계를 따로 고려하지 않고 카운트만 하면 같은 레벨이 되었을 때 우선순위를 정하지 못하고 그대로 출력되기 때문이다.

 

반례는 아래와 같다.

3 2
1 3
2 1
-> 답 2 1 3

Map, Key 풀이는 
1 -> level : 1
2 -> level : 0
3 -> level : 1
-> 레벨이 같으면 무작위로 출력되어 2 3 1이 나오는 경우 오답

---

위의 풀이는 a와 b의 관계가 너무 얕다. 아니 없다고 보면 된다. 1 뒤에는 3이 와야되는데 그걸 알 방법이 없다. 그래서 학생 a와 학생 b의 관계를 더 직접적으로 설정해준 다음 위상정렬을 통해 출력해야 한다.

 

그런데 이젠 Map을 굳이 써야할까?

 

내가 Key와 Value를 사용하려는 이유가 없어졌다. 애초에 나의 Map사용 아이디어는 학생의 고유한 Id를 조회할 때마다 그에 따른 학생의 rank를 value에 카운트해주는 용도였다.

 

그런데 연관관계를 설정해야하고 학생 아이디는 N 숫자로 표현되므로 Map으로 Key값 설정할 필요 없이 인접리스트 배열로 나타내주고 위상 정렬을 위한 1차원 배열을 하나 생성하는게 더 편하다. 

 

❐ 풀이 과정 

1) 학생의 키 관계를 등록해줄 List배열과 등수를 매길 rank 1차배열을 생성한다.

2) 앞에 오는 학생 a , 뒤에 오는 학생 b라 할 때, rank[b]를 카운트해준다. (rank[b]=1이면 자신 앞에 1명의 학생이 있어야 한다는 뜻이다.)

3) rank 등수가 제일 높은 0인 노드들을 Queue에 담고 그 뒤에 오는 학생 노드들을 꺼내준다.

4) 뒤에 오는 학생(next)이 조회한다.

   4-1 ) sb.append(pos+" "); 앞에 있는 학생은 줄을 섰으므로 rank[next]의 값을 깎아준다.

   4-2 ) if(rank[next] ==0)  의 뜻은 더 이상 앞에 올 학생이 없다는 뜻이기 때문에 queue에 추가해준다.

   → rank[i] = 2인 경우에는 자신보다 앞에 학생이 2명이 있어야 한다는 소리이다. 그래서 앞에 있는 학생이 나올때마다 rank[i]의 값을 빼줌으로써 값이 0이되면 자신의 차례가 오는 것이다.

 

 

 

풀이 코드 ✔︎ 

모든 그래프가 하나의 루트노드를 기준으로 연결되어 있는 것이 아니므로, 모든 노드를 조회해줘서 여러 개의 루트 노드를 queue에 추가해줘야 한다.

import java.io.*;
import java.util.*;

public class Main {

	static int n,m;
	static List<Integer>[] list;
	static int[] rank;
	static StringBuilder sb;
	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());
		
		list = new ArrayList[n+1];
		rank = new int[n+1];
		sb = new StringBuilder();
		for(int i=0; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<m; i++) {
			st=  new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list[a].add(b);
			rank[b]++;
		}
		
		bfs();
		System.out.println(sb.toString());
	}
	
	static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		
		for(int i=1; i<n+1; i++) {
			if(rank[i] == 0) {
				q.add(i); // 루트노드 
			}
		}
			
		while(!q.isEmpty()) {
			int pos = q.poll();
			
			sb.append(pos+" ");
			for(int next : list[pos]) {
				rank[next]--;
				if(rank[next]==0) {
					q.add(next);
				}
			}
		}
		
		
		
	}
}