백준 No.2252 줄 세우기 - JAVA

 

 

해당 문제는 위상정렬을 알고 풀어야 했던 문제이다.

 

위상정렬

어떤 일을 하는 순서를 찾는 알고리즘이다. -> 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

 

위상정렬(Topological Sort)의 특징

-> 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. (사이클 안됨)

-> 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라 한다.

-> 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중된되고 이러한 그래프로 표현된 문제는 실행이 블가능한 문제가 된다.

 

 

위상정렬(Topological Sort)의 진행

1. 진입차수(Indegree)가 0인 정점(자신에게 들어오는 간선의 수 0)을 선택

   - 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다.

   - 초기에 간선의 수가 0인 모든 정점을 큐에 삽입한다.

2. 선택된 정점과 여기에 부속된 모든 간선을 삭제한다.

    - 선택된 정점을 큐에서 삭제

    - 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소 (그래프가 삭제되었으니 그 그래프가 가리키는 간선은 삭제)

 

3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘은 종료된다.

 

 

줄 세우기 문제 코드로 본 위상정렬

인접리스트로 그래프를 구현한다 그리고 방향이 있는 그래프이기에 indegree가 몇인지 파악할 수 있도록 indegree 배열을 생성한다. 0부터 시작이 아닌 1부터 시작이므로 주어진 배열 크기에 +1을 한다.

수는 두 개가 계속해서 M만큼 주어진다. 그래서 for문을 돌리고 받은 두 수를 인접 리스트에 삽입한다.

만약 1  2 가 주어진다면 1번 그래프가 2번 그래프를 가리킨다는 뜻으로 넣는다.

graph.get(1).add(2)   --> list에 인덱스가 그래프에 번호를 나타낸다. 1번 그래프는 1번 인덱스를 차지한다고 보면된다.

Queue를 만들고 진압차수 중에 0인 값을 찾아 모두 Queue에 담는다. 

그렇게 담은 Queue가 비지 않을 때까지 반복하여 하나씩 뽑는다. 그리고 뽑은 값은 삭제하는 개념이므로 뽑은 그래프가 가리키는 간선들은 모두 삭제되어야 한다. 인접리스트로 구현했기 때문에 graph.get(1) 으로 그 그래프가 가리키는 그래프들을 모두 불러와 for문을 동작심킨다. 그러면서 간선을 삭제하므로 indegree도 물론 감소해야한다. 감소시켰는데 그 값이 0이 된다면 Queue에 담게 되고 이 과정을 모두 반복하면서 위상정렬이 마무리된다. 

 

package com.example.algorithgm.topologicalSort;

import java.io.*;
import java.util.*;

public class LineSort {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int indegree[] = new int[N + 1];
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

        // 위상정렬에 사용할 그래프 2차원 리스트로 구현
        for(int i =0 ; i<= N+1 ; i++){
            graph.add(new ArrayList<Integer>());
        }

        // 2차원 리스트의 인덱스가 학생번호이다.
        // 주어진 키 비교정보에 따라 2차원 리스트 정보를 초기화한다.
        // 리스트 초기화 하면서 진입차수 배열 ㄱ밧도 추가해줘야함
        for (int i = 0;i< M;i++){
            String[] temp = br.readLine().split(" ");
            graph.get(Integer.parseInt(temp[0])).add(Integer.parseInt(temp[1]));
            indegree[Integer.parseInt(temp[1])]++;
        }


        Queue<Integer> q = new LinkedList<>();
        for(int i=1;i<indegree.length;i++){
                if(indegree[i] == 0){
                    q.offer(i);
                }
        }

        while(!q.isEmpty()){
                int stNumber = q.poll();
                bw.write(stNumber + " ");
                //진입차수가 0인 그래프를 Q에 넣고 뻇으니 방향 간선들이 모두 사라지므로 for문
                for(int std : graph.get(stNumber)){

                    indegree[std]--;    //진입차수를 빼줘야한다.
                    if(indegree[std] == 0){
                         q.offer(std);
                    }
                }
          }

            bw.flush();

    }
}

 

 

참고

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

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

2252번: 줄 세우기