728x90
반응형
2252 - 줄 세우기
https://www.acmicpc.net/problem/2252

문제
N명의 학생 키 순서대로 줄 세움
두 학생의 키를 비교하는 방법 사용 (모든 학생 다 비교 X 일부 O)
=> 일부 학생들의 키 비교한 결과 주어졌을 때 줄 세우는 프로그램
입력
첫째 줄: N (1 <= N <= 32,000), M (1 <= M <= 100,000, 키를 비교한 횟수)
다음 M개의 줄: 키를 비교한 두 학생의 번호 A, B (A가 B 앞에 서야 함)
(학생들의 번호 1 ~ N번)
출력: 학생들을 앞에서부터 줄을 세운 결과(답 여러 가지인 경우 아무거나 출력)
풀이
위상정렬(Topological Sort)
방향이 있는 비순환 그래프(DAG; Directed Acyclic Graph)에서 모든 간선의 방향 지키며 정점 나열하는 것
- 모든 정점의 진입차수(in-degree) 계산 -> 들어오는 간선 개수
- 진입차수 0인 노드(= 앞에 올 게 X 노드)를 큐에 삽입
- 큐에서 하나씩 꺼내 결과 리스트에 추가
- 해당 노드가 가리키는 노드의 진입차수 1 감소
- 새롭게 진입차수 0이 되면 큐에 추가
- 큐가 빌 때까지 계속
- `graph[a]`: a 학생보다 뒤에 서야 하는 학생들의 리스트 (a -> b 방향 간선 표현)
- `inDegree[b]`: b로 들어오는 간선 = b 앞에 서야 할 사람 수
- ex. 4 2 -> `graph[4].add(2)` / `inDegree[2]++`: 2는 4 뒤에 서야 함
- 진입차수 0 = 아무도 자신 앞에 서지 않아도 되는 학생 -> 줄 맨 앞에 올 수 있음
-> 큐에 먼저 넣고 하나씩 꺼내며 순서 정함 - BFS 기반 위상 정렬
- 큐에서 학생 꺼냄 -> 앞에 설 사람 X -> 순서에 추가
- 그 학생이 가리키는 다음 학생(`next`)의 진입차수 감소
-> 앞에 서야 할 사람 하나 빠짐 - IF. 진입차수 0 -> 그 학생도 줄 설 수 있음 -> 큐에 추가
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++) {
// 진입차수 0
if (inDegree[i] == 0) q.offer(i);
}
while (!q.isEmpty()) {
int cur = q.poll();
sb.append(cur).append(' ');
for (int next : graph[cur]) {
inDegree[next]--;
if (inDegree[next] == 0) q.offer(next);
}
}
코드
import java.io.*;
import java.util.*;
// 줄 세우기
public class boj_2252 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
List<Integer>[] graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
int[] inDegree = new int[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
graph[A].add(B);
inDegree[B]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) q.offer(i);
}
while (!q.isEmpty()) {
int cur = q.poll();
sb.append(cur).append(' ');
for (int next : graph[cur]) {
inDegree[next]--;
if (inDegree[next] == 0) q.offer(next);
}
}
System.out.println(sb);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Dijkstra] 백준 1504 - 특정한 최단 경로 (Java) (0) | 2025.11.11 |
|---|---|
| [BOJ/MST] 백준 1647 - 도시 분할 계획 (Java) (0) | 2025.11.11 |
| [BOJ/DFS+DP] 백준 2533 - 사회망 서비스(SNS) (Java) (0) | 2025.11.10 |
| [BOJ/BFS] 백준 16954 - 움직이는 미로 탈출 (Java) (0) | 2025.11.10 |
| [BOJ/Union-Find] 백준 4195 - 친구 네트워크 (Java) (0) | 2025.11.10 |