반응형
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
위상정렬을 이용한 문제다.
정점 1의 간선이 정점 3에 방향그래프로 연결되어있다면 1을 처리해준 후 3을 정렬시켜 주면된다.
만약 정점 3을 향해 연결된 정점 2가 하나 더 있다면 정점 3은 정점 2 이후에 나열될 수 있다.
정점1과 정점2는 순서가 없으므로
1 -> 2 -> 3
2 -> 1 -> 3
둘다 가능하므로 나열하는 순서는 뒤바뀔 수 있다.
"자신에게 들어오는 간선이 없는 정점"을 확인하기 위해 int 배열을 만들어 준다.
ex) 0, 1, 2, 0, 0 // b에 들어오는 간선 1개, c에 들어오는 간선 2개
처음에 0인 정점을 q에 넣고, 큐를 순회하며 간선이 있다면 향하는쪽 정점을 1씩 줄여주면 된다.
정점이 0이 되면 큐에 넣는다. // 0이 될때는 딱 한번이다. inDegree 를 이미 세주었기 때문에.코드 구현
|
import java.io.*;
import java.util.*;
public class TopologySort {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static List<List<Integer>> list = new ArrayList<>();
static Queue<Integer> q = new LinkedList<>();
static int[] isZero;
public static void main(String[] args) throws IOException {
List<Integer> order = new ArrayList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
int student = Integer.parseInt(st.nextToken());
int lines = Integer.parseInt(st.nextToken());
isZero = new int[student+1];
// 0번은 사용하지 않음.
for(int i = 0; i<=student; i++)
list.add(new ArrayList<>());
// 그래프
while(lines-- > 0){
st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
++isZero[second];
list.get(first).add(second);
}
// 위상정렬
for (int i = 1; i < isZero.length; i++) { // 모든 edge 확인
if (isZero[i] == 0)
q.add(i);
}
while (!q.isEmpty()) { // 현재 0인 edge
int edge = q.poll();
order.add(edge);
List<Integer> v = list.get(edge);
for (int e : v) {
isZero[e]--;
if (isZero[e] == 0) { // 0이 됐을때 q에 넣는다.
q.add(e);
}
}
}
order.forEach((n) -> System.out.print(n + " "));
}
}
|
cs |
반응형
'문제풀이 > 코딩 문제 풀이' 카테고리의 다른 글
| [백준] 1253번 좋다 (JAVA) (0) | 2022.04.19 |
|---|---|
| [백준] 13418 학교 탐방하기 (JAVA) (0) | 2022.04.15 |
| [백준] 1992번 쿼드트리 (JAVA) (0) | 2022.03.20 |
| [백준] 2448번 별 찍기 - 11 (JAVA) (0) | 2022.03.19 |
| [백준] 7576번 토마토 (JAVA) (0) | 2022.03.18 |