위상정렬 자바로 구현하기, 백준2252_줄 세우기

위상 정렬은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. (위키 정의)

 

순서가 있는 노드를 차례대로 수행할 때에 쓰인다.

 

1 -> 3

2 -> 3    3 -> 4    다음과 같이 있는데, 2번을 수행하지 않았는데 4번이 먼저 나오게 된다면 오류라는 것이다.

순서에 맞지 않기 때문이다. 이러한 이유 때문에 위상 정렬을 사용하기 위한 전제는

 

싸이클이 없어야만 사용가능하다. 1->2->3->1  이러면 어느점이 시작점인지도 모르는 싸이클 그래프이다.

싸이클하지 않은 이 그래프를 DAG(Directed Acyclic Graph) 라고 부른다. (방향성 비순환 그래프)

 

구현 방식을 설명하고 바로 백준 문제로 예시를 들며 풀겠다.

 

1. 정점과 간선의 개수를 입력 받는다.

2. 결과를 받아줄 리스트나 배열을 정의한다. 밑의 코드에는 result로 사용했음

3. 한 정점에서 뻗어나가 선택된 정점을 저장해주기 위해 ArrayList 배열을 선언한다.

4. 한 정점이 선택받은 횟수를 저장할 배열을 선언한다.

5. Queue를 하나 정의 한다.

6. 선택받은 횟수가 0인 녀석들을 queue 안에 집어 넣어준다.

7. queue가 not empty 할 때까지 while 문을 돌린다.

  7-1. queue에서 하나씩 꺼내어서 연산을 수행하는데(꺼낸 놈들은 result 안에 집어넣는다), 이 녀석들이 뻗어나간 정점들이 선택받은 횟수에서 1을 차감한다. 이 녀석들이 그 값이 0이 되었다면 queue에 추가한다. 

 

 

Q: 왜 선택받은 횟수가 0인 녀석들을 queue안에 집어넣나요??

 

A: 시작점으로 볼 수 있기 때문이다. 이 시작점들의 간선을 없애주는 작업이 곧 선택받은 횟수를 1씩 차감하는 것으로 표현한다. 그리고 그 정점이 선택받은 횟수가 0이라면 이게 곧 다시 시작점이 되게된다.

 

이러한 방법으로 한 다면 위의 예시로 든 

1 -> 3

2 -> 3    3 -> 4  이 부분에서 1을 수행하여 3이 선택받은 횟수를 1줄인다 하더라도 2가 3을 여전히 선택하고 있기에 3이 선택받은 횟수는 0이 되지않는 반면 2는 선택받은 횟수가 0이기 때문에 2부터 queue안에 들어가게 될 것이다.

 

 

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class boj_2252 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> result =new ArrayList<>();       //결과 값 저장하는 list
        Queue<Integer> que = new LinkedList<>();            //수행을 위한 큐
        int n = sc.nextInt();                               //점의 개수
        int m = sc.nextInt();                               //간선의 개수
        int[] targeted=new int[n+1];                        //선택받은 횟수를 저장하기 위한 배열 n+1로 설정하여 [0]을 패스했다.
        ArrayList<Integer>[] direction=new ArrayList[n+1];  //해당 점이 선택한 다른 점들을 저장하기 위한 arraylist 배열
        for (int i = 0; i < n+1; i++) {
            direction[i] = new ArrayList<>();               //배열 당 arraylist 선언
        }
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();                       //시작 점 입력
            int end = sc.nextInt();                         //가리킨 점 입력
            targeted[end]++;                                //가리킨 점의 선택받은 횟수 추가
            direction[start].add(end);                      //시작 점이 선택한 점 list에 가리킨 점 추가
        }
        for (int i = 1; i <= n; i++) {
            if(targeted[i]==0) que.add(i);                  //시작 점들 큐에 다 집어 넣는 작업
        }
 
        while (!que.isEmpty()) {
            int currentNode = que.poll();                   //큐에서 하나 빼내어 result에 추가
            result.add(currentNode);
            for (int i = 0; i < direction[currentNode].size(); i++) {
                int getArrowNode = direction[currentNode].get(i);   //가리킨 점을 가지고 와서 그 점의 선택받은 횟수 차감 후 그 값이 0이면 큐에 추가
                targeted[getArrowNode]--;
                if (targeted[getArrowNode] == 0) {
                    que.add(getArrowNode);
                }
            }
        }
        for (Integer ans : result) {
            System.out.println(ans+" ");
        }
    }
}