1. μ μ π§
μμ μ λ ¬(Topology Sort)μ΄λ μμκ° μ ν΄μ Έ μλ μμ μ μ°¨λ‘λλ‘ μνν λ κ·Έ μμλ₯Ό κ²°μ ν΄ μ£Όλ μκ³ λ¦¬μ¦μ΄λ€.
κ΅μ‘κ³Όμ μ μ μκ³Όλͺ©μ΄ μμ μ λ ¬μ μ€λͺ νλ κ°μ₯ μ μ ν μμμ΄λ€. μ»΄ν¨ν° 곡νμ μ 곡νκ³ μλ νμμ λ€μ μ 곡과λͺ©(ex. μκ³ λ¦¬μ¦)μ λ£κΈ° μν΄μλ μ μ κ³Όλͺ©(ex. μλ£κ΅¬μ‘°)μ νμμ μΌλ‘ λ€μ΄μΌ νλ€.
κΈ°μ΄μ»΄ν¨ν°νλ‘κ·Έλλ° → μλ£κ΅¬μ‘° → μκ³ λ¦¬μ¦
μλ£κ΅¬μ‘° → λ Όλ¦¬νλ‘λ°μ€κ³ → λ Όλ¦¬νλ‘μ€ν
μκ³ λ¦¬μ¦ → λ Όλ¦¬νλ‘λ°μ€κ³ → λ Όλ¦¬νλ‘μ€ν
λν, μμμ λ ¬μ μμ κ°μ΄ μ¬λ¬ κ°μ κ²½λ‘κ° μ‘΄μ¬ν μ μλ€.
λ§μ§λ§ νΉμ§μΌλ‘λ μμ μ λ ¬μ λΉμν μ ν₯ κ·Έλν(DAG - Directed Acyclic Graph)μλ§ μ μ©μ΄ κ°λ₯νλ€. μ¦, μ¬μ΄ν΄μ΄ λ°μνμ§ μλ λ°©ν₯ κ·Έλνμ¬μΌ νλ€.
2. λμ λ°©μ(BFS) π₯€
μμ μ λ ¬μ BFSμ DFSλ₯Ό ν΅ν΄ ꡬνν μ μλ€. μ°μ BFSλ₯Ό μ΄μ©νλ λ°©λ²μ λ¨Όμ μμ보μ.
BFSλ₯Ό μ΄μ©νλ κ²½μ° μ§μ μ°¨μμ Queueλ₯Ό νμ©νλ€. λμ λ°©μμ μλμ κ°λ€.
[λμ λ°©μ]
- μ§μ μ°¨μκ° 0μΈ μ μ μ Queueμ λ£λλ€.
- Queueμμ μμμ μ°κ²°λ κ°μ μ μ κ±°νλ€.
- κ°μ μ΄ μ κ±°κ° λ ν μ§μ μ°¨μκ° 0μ΄ λ μ μ μ Queueμ λ£λλ€.
- Queueκ° λΉ λκΉμ§ 2λ²κ³Ό 3λ²μ λ°λ³΅νλ€.
μμ μ΄ λλ ν λͺ¨λ μ μ μ λ°©λ¬Ένλ€λ©΄ μμ μ λ ¬μ΄ κ°λ₯ν κ·Έλνμ΄κ³ κ·Έλ μ§ λͺ»ν μν©μ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ κ²½μ°μ΄λ€. μλμ μμ μ λ ¬μ΄ κ°λ₯ν μμμ μμ μ λ ¬μ΄ λΆκ°λ₯ν μμλ₯Ό ν΅ν΄ νλ² λ μ΄ν΄λ₯Ό μ΄ν΄λ³΄μ.
[μμ μ λ ¬μ΄ κ°λ₯ν μμ]
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | 0 | 0 | 1 | 2 | 1 | 2 |
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | λ°©λ¬Έ | λ°©λ¬Έ | 0 | 0 | 1 | 2 |
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | 0 | 1 |
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | 0 |
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ | λ°©λ¬Έ |
[μμ μ λ ¬μ΄ λΆκ°λ₯ν μμ]
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | 0 | 0 | 2 | 3 | 1 | 1 |
μ μ | 1 | 2 | 3 | 4 | 5 | 6 |
μ§μ μ°¨μ | λ°©λ¬Έ | λ°©λ¬Έ | 1 | 1 | 1 | 1 |
μ¬μ΄ν΄μ΄ μμΌλ©΄ μμ§ λ°©λ¬Έμ νμ§ λͺ»νμ§λ§ μ μ λ€μ μ§μ μ°¨μκ° 0μ΄ μλλΌμ λ μ΄μ λ°©λ¬Έμ νμ§ λͺ»νλ μν©μ΄ λ°μνλ€. μ¦, λͺ¨λ μ μ μ λ°©λ¬Ένμ§ λͺ»ν κ²½μ°λ μ¬μ΄ν΄μ΄ μμ΄μ μμ μ λ ¬μ΄ λΆκ°λ₯ν μν©μ΄λΌκ³ ν μ μλ€.
3. BFSλ₯Ό μ΄μ©ν ꡬν μ½λ (JAVA) πΉ
첫 μ€μλ μ μ μ κ°μμ κ°μ μ κ°μλ₯Ό λ°μμ¨λ€. κ·Έλ¦¬κ³ κ°μ μ κ°μλ§νΌ μΆλ° μ μ κ³Ό λμ°© μ μ λ€μ 보μ¬μ€λ€. μλλ μμμ μ΄ν΄λ³Έ μμλ₯Ό μ λ ₯μΌλ‘ λνλΈ κ²μ΄λ€.
6 6
1 3
1 4
2 4
3 5
4 6
5 6
public class TopologySorting {
static int N, M;
static Node[] adjNode;
static int[] inDegree;
static class Node {
int vertex;
Node link;
public Node(int vertex, Node link) {
super();
this.vertex = vertex;
this.link = link;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// μΈμ 리μ€νΈ
adjNode = new Node[N + 1];
// μ§μ
μ°¨μ
inDegree = new int[N + 1];
int from, to;
for(int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine(), " ");
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
// μΈμ 리μ€νΈ μΆκ°
adjNode[from] = new Node(to, adjNode[from]);
// μ§μ
μ°¨μ μΆκ°
inDegree[to]++;
}
// μμ μ λ ¬μ ν΅ν΄ μ»μ΄μ§ κ²½λ‘λ₯Ό
// resultFromTopologySortμ μ μ₯
ArrayList<Integer> resultFromTopologySort = topologySortByBFS();
if(resultFromTopologySort.size() == N) {
System.out.println("μμ μ λ ¬ κ°λ₯");
for(Integer i : resultFromTopologySort) {
System.out.print(i + " ");
}
}
else {
System.out.println("μμ μ λ ¬ λΆκ°λ₯ (μ¬μ΄ν΄ λ°μ)");
}
}
static ArrayList<Integer> topologySortByBFS(){
Queue<Integer> queue = new ArrayDeque<>();
// μ§μ
μ°¨μκ° 0μΈ μ μ μΆκ°
for(int i = 1; i <= N; i++) {
if(inDegree[i] == 0)
queue.offer(i);
}
ArrayList<Integer> visitedNode = new ArrayList<>();
while(!queue.isEmpty()) {
int currentNode = queue.poll();
visitedNode.add(currentNode);
for(Node temp = adjNode[currentNode]; temp != null; temp = temp.link) {
// μ°κ²°λ κ°μ μ μ κ±°ν΄μ£Όλ νμ
inDegree[temp.vertex]--;
// μ§μ
μ°¨μκ° 0μ΄ λ κ²½μ°
if(inDegree[temp.vertex] == 0) {
queue.offer(temp.vertex);
}
}
}
return visitedNode;
}
}
4. λμ λ°©μ(DFS) πΈ
DFSλ₯Ό μ΄μ©νλ κ²½μ° μ§μ μ°¨μμ λ°©λ¬Έ μ¬λΆλ₯Ό νμ©νλ€. DFSμ κ²½μ° Stackμ μ΄μ©νλ λ°©λ²λ μλ€. Stackμ μ΄μ©νλ©΄ κ²½λ‘λ₯Ό μ½κ² μ μ μμ§λ§ μ¬μ΄ν΄ λ°μ μ¬λΆλ₯Ό μκΈ° μ΄λ ΅λ€. κ·Έλμ μ΄λ² κΈμμλ μμ μ λ ¬μΈμ§ μλμ§λ₯Ό μ½κ² μμ보기 μνμ¬ μ§μ μ°¨μμ λ°©λ¬Έμ¬λΆλ₯Ό μ¬μ©νλ λ°©μμ μ΄μ©ν΄ 보μ. (λ¬Όλ‘ μ΄ λ°©λ²λ κ²½λ‘λ₯Ό νμΈν μ μλ€.)
[λμ λ°©μ]
- μ§μ μ°¨μκ° 0μΈ μ μ μ λ¨Όμ λ°©λ¬Ένλ€.
- DFS λ°©μμ μ΄μ©νμ¬ κ³μν΄μ λ€μ μ μ μΌλ‘ μ§ννλ€.
μ΄λ, λ°©λ¬Έ μ¬λΆλ₯Ό νμν΄ μ€λ€. - λ μ΄μ μ§νν μ μμΌλ©΄ λ°©λ¬Έ μ¬λΆλ₯Ό ν΄μ νλ©΄μ λμμ¨λ€.
- μμ§ λ°©λ¬Ένμ§ μμ μ§μ μ°¨μ 0μΈ μ μ λ€μ κΈ°μ€μΌλ‘ 1~3 κ³Όμ μ λ°λ³΅νλ€.
λ§μ½ 2λ²μ κ³Όμ μμ λ€μ μ μ μ΄ μ΄λ―Έ λ°©λ¬Έν μ μ μ΄λΌλ©΄ μ¬μ΄ν΄μ΄ λ°μνλ κ·Έλνμ΄λ€. μ¦, μμ μ λ ¬μ΄ λΆκ°λ₯ν κ·Έλνμ΄λ€.
μμ μ λ ¬μ΄ κ°λ₯ν μμμ μμ μ λ ¬μ΄ λΆκ°λ₯ν μμλ₯Ό ν΅ν΄ λ€μ νλ² μμ보μ. μ§ννλ©΄μ 방문체ν¬λ₯Ό ν΄μ£Όκ³ λμμ€λ©΄μ λ°©λ¬Έ μ²΄ν¬ ν΄μ νλ κ²μ μ κΈ°μ΅νμ. κ·Έλ¬λ©΄ κ·Έλ¦Όμ ν΅ν΄ μ½κ² μ΄ν΄ν μ μμ κ±°λΌκ³ μκ°νλ€.
[μμ μ λ ¬μ΄ κ°λ₯ν μμ]
1λ² κ²½λ‘ : 1 → 3 → 5 → 6
2λ² κ²½λ‘ : 1 → 4 → 6
3λ² κ²½λ‘ : 2 → 4 → 6
[μμ μ λ ¬μ΄ λΆκ°λ₯ν μμ]
μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ κ²½μ°λ μ΄ν΄λ³΄μ. μμμ μΈκΈν κ²μ²λΌ λ°©λ¬Έ νμκ° λ κ³³μ μ¬λ°©λ¬Ένλ€λ©΄ μ¬μ΄ν΄μ΄ λ°μνλ κ²μ΄λ€.
5. DFSλ₯Ό μ΄μ©ν ꡬν μ½λ(JAVA) π·
ν΄λΉ λ°©λ²μ μ λ ₯ λν μ μ μ κ°μμ κ°μ μ κ°μλ₯Ό λ°μμ€κ³ , κ°μ μ κ°μλ§νΌ μΆλ° μ μ κ³Ό λμ°© μ μ μ λνλΈλ€κ³ νμ. μλμ μ λ ₯μ μμ μ λ ¬μ΄ λΆκ°λ₯ν κ·Έλνμ μ λ ₯μ΄λ€. (μμ μ λ ¬μ΄ κ°λ₯ν κ·Έλνμ μ λ ₯μ BFSλ₯Ό μ΄μ©ν ꡬν μ½λμμ μ°Έκ³ ν μ μλ€.)
6 7
1 3
1 4
2 4
3 5
4 3
5 6
6 4
public class TopologySortingByDFS {
static int N, M;
static Node[] adjNode;
static boolean[] visited;
static boolean isCycle;
static int[] inDegree;
static class Node {
int vertex;
Node link;
public Node(int vertex, Node link) {
super();
this.vertex = vertex;
this.link = link;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// μΈμ 리μ€νΈ
adjNode = new Node[N + 1];
// μ§μ
μ°¨μ - μΆλ°μ μ νμΈνκΈ° μν κ²
inDegree = new int[N + 1];
// λ°©λ¬Έ μ²΄ν¬ - μ¬μ΄ν΄ λ°μ μ¬λΆλ₯Ό νμΈνκΈ° μν κ²
visited = new boolean[N + 1];
int from, to;
for(int i = 0; i < M; i++) {
st = new StringTokenizer(in.readLine(), " ");
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
// μΈμ 리μ€νΈλ₯Ό λ§λ€κΈ°
adjNode[from] = new Node(to, adjNode[from]);
// μ§μ
μ°¨μ μΆκ°
inDegree[to]++;
}
topologySortByDFS();
if(isCycle) {
System.out.println("μμ μ λ ¬ λΆκ°λ₯ (μ¬μ΄ν΄ λ°μ)");
}
else {
System.out.println("μμ μ λ ¬ κ°λ₯");
}
}
static void topologySortByDFS(){
for(int i = 1; i <= N; i++) {
if(inDegree[i] == 0) {
visited[i] = true;
dfs(i);
visited[i] = false;
}
}
}
static void dfs(int current) {
// λ§μ§λ§ μ μ μΈ κ²½μ°
if(adjNode[current] == null) {
return;
}
for(Node temp = adjNode[current]; temp != null; temp = temp.link) {
// μ¬μ΄ν΄μ΄ λ°μνλ κ²½μ°
if(visited[temp.vertex]) {
isCycle = true;
return;
}
visited[temp.vertex] = true;
dfs(temp.vertex);
visited[temp.vertex] = false;
}
}
}
6. μκ°λ³΅μ‘λ π§
μμ μ λ ¬μ ν λ 'μ μ μ κ°μ + κ°μ μ κ°μ'λ§νΌ μκ°μ΄ μμλλ€. κ·Έλ¬λ―λ‘ μμ μ λ ¬μ μκ° λ³΅μ‘λλ O(V + E)μ΄λ€.
ν΄λΉ κΈμ
λλλΉλμ μμ μ λ ¬(Topology Sort)
yoongrammerλμ μμ μ λ ¬(Topological sort) κ°λ λ° κ΅¬ν
Topological Sorting using Kahn's Algorithm
μ μ°Έκ³ νμμ΅λλ€.
'π μλ£κ΅¬μ‘° > μ λ ¬' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
ν΅ μ λ ¬ (Quick Sort) (0) | 2023.03.20 |
---|---|
ν μ λ ¬ (Heap Sort) (0) | 2023.03.12 |
λ³ν© μ λ ¬(Merge Sort) (0) | 2023.03.07 |
μ½μ μ λ ¬(Insertion Sort) (0) | 2023.03.06 |
μ ν μ λ ¬(Selection Sort) (2) | 2023.03.04 |