https://www.acmicpc.net/problem/2252
알고리즘 분류 : 그래프 이론, 위상 정렬, 방향 비순환 그래프
❓문제
🔅해석
위상정렬을 이용하여 풀이한다.
위상정렬은 비순회 방향 그래프에서 정점을 정렬하는 방식이며, 동일한 우선순위를 가진 작업들이 여러 가지 방법으로 나열될 수 있기 때문에 여러 개의 정렬 결과가 나올 수 있다.
// input
4 2
4 2
3 1
1. indegree 계산 및 indegree 배열 중에서 0인 노드를 Queue에 담는다.
2. Queue에서 pop를 하고, 3(pop 한 값)과 연결된 노드에 indegree를 하나 감소시킨다.
3. Queue에서 pop를 하고, 4(pop 한 값)와 연결된 노드에 indegree를 하나 감소시킨다.
4. Queue가 빌 때까지 반복한다.
⭕정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static ArrayList<Integer>[] adjList;
static int[] indegree;
static Queue<Integer> que;
static StringBuilder sb = new StringBuilder();
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());
adjList = new ArrayList[N];
for (int n = 0; n < N; n++) {
adjList[n] = new ArrayList<>();
}
que = new LinkedList<>();
indegree = new int[N];
// 1. in-degree 계산
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
adjList[a].add(b);
indegree[b]++;
}
for (int i = 0; i < N; i++) {
if (indegree[i] == 0) {
que.add(i);
}
}
// 2. loop
while (!que.isEmpty()) {
int node = que.poll();
sb.append(node + 1).append(" ");
for (Integer i : adjList[node]) {
indegree[i]--;
if (indegree[i] == 0) {
que.offer(i);
}
}
}
System.out.println(sb.toString());
br.close();
}
}
❗결과
'코딩테스트 > 백준' 카테고리의 다른 글
[코테] 백준 11438번 : LCA 2 (java) (0) | 2024.08.16 |
---|---|
[코테] 백준 1922번 : 네트워크 연결 (java) (0) | 2024.08.15 |
[코테] 백준 3830번 : 교수님은 기다리지 않는다 (java) (0) | 2024.08.15 |
[코테] 백준 1717번 : 집합의 표현 (java) (0) | 2024.08.15 |
[코테] 백준 1202번 : 보석 도둑 (java) (0) | 2024.08.04 |