Baekjoon 2252 줄 세우기 JAVA

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

2252번: 줄 세우기

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202252

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 학생 수가 주어지고 두 학생들 간 키 비교가 주어졌을 때

학생을 키 순서대로 줄 세운 결과를 출력하는 문제다.

​

해당 문제는 위상 정렬이라는 알고리즘을 적용하여 해결했다.

​

입력 처리를 해주고, 비교 정보를 넣어줄 때 큰 친구에 대해서 가리키는 배열 값을 1 증가시키고

이후 만약 아무도 가리키지 않은 애들(작은 애들)에 대해선 큐에 삽입을 하고

큐에서 빼내면 출력값에 추가해 주며,

갈 수 있는 곳에 대해서는 가리키는 배열 값을 1씩 감소시키고 만약 가리키는 배열 값이 0이 되었다면

해당 친구를 큐에 넣어준다.

​

이후 모든 연산이 끝나면 출력해 준다.

​

아래와 같은 테케의 경우

5 5

1 3

2 3

2 4

3 5

4 5

1,2는 자신을 가리키는 경우가 없고 3은 1,2가 가리키고 4는 2가 5는 3,4가 가리키고 있다.

처음 1,2 가 큐에 들어가서 1 2 순으로 출력값에 추가하며

1에선 3에 갈 수 있어 1감소 시키지만 카운트 값은 1이기 때문에 다음을 실행하고

2에서 3에 가기 때문에 3값이 0이 되어 큐에 3 이 들어갈 것이고,

2에선 4에도 갈 수 있어서 큐에 4도 들어간다.

이후 3 4를 빼오면서 출력값에 추가되며 최종적으로 3에서 한번 4에서 한번 5카운트를 감소하기 때문에

최종적으로 5도 큐에 삽입되어 출력값에 추가되어

최종적으로 1 2 3 4 5 가 출력된다.