2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
문제코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class boj2252 {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer infoToken = new StringTokenizer(reader.readLine());
int students = Integer.parseInt(infoToken.nextToken());
int compares = Integer.parseInt(infoToken.nextToken());
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < students + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i <compares; i++) {
StringTokenizer edgeToken = new StringTokenizer(reader.readLine());
int start = Integer.parseInt(edgeToken.nextToken());
int end = Integer.parseInt(edgeToken.nextToken());
adjList.get(start).add(end);
}
// 1. 진입 차수 정리
int[] inDegrees = new int[students + 1];
for (List<Integer> neighbors: adjList) {
for (int neighbor: neighbors) {
inDegrees[neighbor]++;
}
}
// 2. 진입 차수에 따른 첫 정점 정하기
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i < students + 1; i++) {
if (inDegrees[i] == 0) queue.offer(i);
}
// 3. Queue 를 이용 위상정렬 진행
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
for (int neighbor: adjList.get(node)) {
inDegrees[neighbor]--;
if (inDegrees[neighbor] == 0) queue.offer(neighbor);
}
}
// 정답 출력
StringBuilder answer = new StringBuilder();
for (int node: result) answer.append(node).append(' ');
System.out.println(answer);
}
public static void main(String[] args) throws IOException {
new boj2252().solution();
}
}
출력 결과
입력
3 2
1 3
2 3
출력
1 2 3
'Algorithm' 카테고리의 다른 글
백준 15652 N과 M (4) (0) | 2023.07.19 |
---|---|
백준 15651 N과 M (3) (0) | 2023.07.19 |
백준 5904 Moo 게임 (0) | 2023.07.17 |
백준 1417 국회의원 선거 (0) | 2023.07.17 |
백준 2738 행렬 덧셈 (0) | 2023.07.16 |