위상정렬 (Topological sort)
방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬
그래프 안에서 사이클이 존재하는 경우엔, 위상정렬을 적용할 수 없다.
근데, 사이클이 존재한다는 뜻이 무슨 뜻일까?
위와 같은 그래프가 존재한다고 가정할 떄, A->B->C->A... 이런식으로 다시 돌아올 때를 사이클이 존재한다고 한다.
즉, 한 노드에서 다른 노드들을 거쳐 처음 노드로 돌아오는 경우, 사이클이 존재한다고 얘기할 수 있다.
위와 같은 그래프가 주어졌을 때, 어떤 노드를 먼저 우선적으로 방문해야 할까?
우선적으로, indegree 배열을 만들어서 각 노드의 indegree 개수를 확인해보자.
A | B | C | D | E | F | G |
0 | 3 | 0 | 1 | 2 | 1 | 0 |
indegree가 0인 정점을 살펴보면 A,C,G 노드가 해당한다.
큐를 선언해서 A를 먼저 넣고, 정점 A를 제거했을 때 indegree가 0인것은 C,G인데 이중에서 C를 먼저 선택하면 정점 C가 삭제되고, 또 이 때 indegree가 0인것을 살펴보면 D와 G가 된다.
이 때, D의 Indegree가 0이 되는 것은 정점 C를 삭제하며 간선이 사라졌기 때문이다.
이런식으로 결과를 출력한다면,
A C D G E B F
이런식으로 순서가 정해지게 된다.
이 과정을 코드로 나타내면,
A B 이런식으로 입력값이 주어진다면 A <- B 이런식으로 관계가 성립한다고 가정하자.
순서
- 그래프를 입력받을 때 idg 배열의 count를 1 증가시켜준다. (이 때, 두번째로 받는 입력값의 count를 증가시켜줘야 함. 문제 요구 사항에 따라 확인)
- 큐를 선언하여 idg 값이 0인 정점들을 큐에 담아준다.
- 큐를 순회하며, 현재 보고있는 노드를 제거해주고, 근처 노드의 idg 값을 1 빼준다.
- 이 떄, 근처 노드의 idg 값이 0이라면, 큐에 다시 넣어준다.
1.
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph.get(u).add(v);
deg[v]++;
}
2.
Queue<Integer> q = new LinkedList<>(); // degree가 0인 정점을 먼저 queue에 넣는다.
for(int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.add(i);
}
}
3 & 4.
while(!q.isEmpty()){
int cur = q.poll();
System.out.println(cur);
for(int nxt : graph.get(cur)) {
deg[nxt]--;
if (deg[nxt] == 0) q.add(nxt);
// System.out.println("nxt: " + nxt);
}
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] Gold IV. 여행 가자 (0) | 2024.08.02 |
---|---|
[백준] Gold V. 집합의 표현 (0) | 2024.07.30 |
[백준] Silver I. 절댓값 힙 (0) | 2024.07.23 |
[백준] Silver II. 생태학 (0) | 2024.07.22 |
[백준] Gold IV. 부분 합 (0) | 2024.07.21 |