백준 2252번: 줄 세우기 문제를 풀다가 위상 정렬 알고리즘에 대해 알게 되었다.
위상정렬 알고리즘의 개념에 대해서 포스팅을 해보았다.
1. 위상 정렬 알고리즘이란?
순서가 정해져 있는 작업을 차례대로 사용해야 할 때 사용하는 알고리즘.
- 사용조건
1) 단방향 그래프여야함.
2) 그래프끼리의 Cycle이 생기지 않아야함.
2. 알고리즘 간략 설명
1) 단방향그래프로 노드 저장
2) 노드를 저장할때 edgeCount값도 같이 저장해준다.(여기서 edgeCount는 노드를 가리키고 있는 간선의 수를 뜻한다.)
3) edgeCount값이 0인 것들을 먼저 큐에 넣고 노드를 방문하면서 edgeCount를 방문할때마다 -1을 해준다.
4) edgeCount값이 0이 되면 큐에 넣는다.
5) 큐에 값이 없을때까지 순회한다.
ex) 예시
[4,2],[4,2],[2,1]의 데이터가 들어올 경우 아래처럼 그래프가 그려진다.
3. 위상정렬을 이용한 대표적인 문제
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
위의 문제는 단방향 그래프에, 키를 비교한 값이기 때문에 서로 사이클이 생기지 않으므로
위상정렬의 알고리즘 조건에 부합한다.
아래는 나의 코드이다.
- 내 풀이
import java.util.*;
public class Main {
static ArrayList<Integer> list = new ArrayList<>();
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
static int[] edgeCount;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();//노드 수
int M = sc.nextInt();//줄 수
Queue<Integer> queue =new LinkedList<>();
int[][] arr= new int[M][2];
for(int i=0;i<M;i++){
arr[i][0]= sc.nextInt();
arr[i][1]= sc.nextInt();
}
edgeCount =new int[N + 1];
//행마다 arraylist 생성
for(int i=0;i<N+1;i++) graph.add(new ArrayList<>());
for(int i=0;i<arr.length;i++){
putGraph(arr[i][0],arr[i][1]);
}
for(int i=1;i<N+1;i++){
if(edgeCount[i]==0){//count값이 0인값 먼저 큐에 넣어준다.
queue.add(i);
}
}
while (!queue.isEmpty()){
int idx = queue.remove();
System.out.print(idx+" ");
ArrayList<Integer> node = graph.get(idx);
for(int i=0;i<node.size();i++){
int next = node.get(i);
edgeCount[next]--;
if(edgeCount[next]==0){
queue.add(next);
}
}
}
}
public static void putGraph(int x,int y){
//포함하고 있지 않다면
if(!graph.get(x).contains(y)) {
graph.get(x).add(y);//단방향 그래프에 추가
edgeCount[y]++;//간선수 카운트 +1
}
}
}'알고리즘' 카테고리의 다른 글
| [알고리즘] 조합(Combination) (0) | 2022.12.02 |
|---|---|
| [알고리즘] 슬라이딩 윈도우 (0) | 2022.09.15 |
| [알고리즘] 정렬1(버블,선택,삽입) (0) | 2022.07.29 |
| [알고리즘] 힙(Heap) (0) | 2022.07.21 |
| [알고리즘] 해시(Hash) (0) | 2022.07.15 |
