[백준] Java - 줄 세우기

2252번: 줄 세우기

백준의 위상정렬 문제 줄 세우기의 자바 풀이다.

 

위와 같이 순서가 정해져 있고 사이클이 없는 그래프를 정렬하는 알고리즘이 위상정렬이다.

 

 "진입 차수"와 "인접 리스트"를 통해서 문제를 해결할 수 있었다.

위의 그림에서 6을 보면 4와 5로부터 진입하는 것을 볼 수 있다. 2개의 노드가 6으로 진입하므로 진입 차수는 2이다.

반대로 1이나 2는 진입차수가 0이다.

 

인접리스트를 통해 연결된 다음 노드를 저장하고 진입차수가 0인 것 부터 큐에 넣어 정렬을 시작한다.

진입 차수가 0인 노드부터 출발하게 되고 한번 탐색된 노드의 진입 차수는 1을 감소시켜 다시 큐에 삽입한다.

 

이렇게 큐를 채워가면서 각 노드의 진입차수가 0이 될 때까지 순차적으로 정렬한다.

 

 

 

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음