BOJ 2252번 줄 세우기 ( 위상 정렬 ) JAVA
풀이
위상정렬을 이용하는 문제입니다.
'답이 여러 가지인 경우에는 아무거나 출력한다' 와 '일부 학생들의 키만을 비교해 보았다' 이 포인트가
위상정렬 문제라는 것을 암시한다.
구현은 위상정렬 그 자체이기 때문에 위상정렬을 한 번 공부한다면 쉽게 해결할 수 있다.
링크
https://www.acmicpc.net/problem/2252
위상정렬 - http://blog.naver.com/PostView.nhn?blogId=ssarang8649&logNo=220988436553
소스 코드
package boj;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Boj2252 {
static int n, m;
static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
static int[] target;
static Queue<Integer> q = new LinkedList<>();
static ArrayList<Integer> ans = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i <= n; i++) {
map.add(new ArrayList<>());
}
target = new int[n + 1];
for (int i = 0; i < m; i++) {
int a, b;
a = sc.nextInt();
b = sc.nextInt();
map.get(a).add(b);
target[b]++;
}
for (int i = 1; i <= n; i++) {
if (target[i] == 0) {
q.add(i);
}
}
while (!q.isEmpty()) {
int cur = q.poll();
ans.add(cur);
for (int next : map.get(cur)) {
target[next]--;
if (target[next] == 0) {
q.add(next);
}
}
}
for (int i = 0; i < n; i++) {
sb.append(ans.get(i)).append(" ");
}
System.out.println(sb);
}
}
'Algorithm' 카테고리의 다른 글
BOJ 1766번 문제집 ( 위상 정렬, 우선순위 큐) JAVA (0) | 2021.04.10 |
---|---|
BOJ 7579번 앱 ( DP, 배낭 문제 ) JAVA (0) | 2021.04.10 |
BOJ 4948번 부분합 ( 투포인터 ) JAVA (0) | 2021.04.09 |
BOJ 2239번 스도쿠 ( 백트래킹 ) JAVA (0) | 2021.04.09 |
BOJ 1238번 파티 ( 다익스트라 ) JAVA (0) | 2021.04.08 |