BOJ 3665 : 최종 순위

www.acmicpc.net/problem/3665

3665번: 최종 순위

문제를 제대로 해석하지 못해서 좀 고생했다.

문제의 조건을 풀어서 설명하면 다음과 같다.

• 기존의 순서가 주어지고, 이후 상대적인 순서의 변경이 주어질 때, 변경된 순서대로 출력
• 만약 불가능하다면, IMPOSSIBLE 출력

처음에 주어진 순서대로 연결해주고, 이후 변경된 순서를 적용시켜서 연결, 진입차수를 수정해주면 된다.

처음 연결에서 인접행렬을 짜듯이 하나하나 연결을 해줘야 하는게 중요하다.

예를 들자면 다음과 같다.

5 4 3 2 1 순으로 처음 순서가 주어질 때,

(5->4), (5->3), (5->2), (5->1), (4->3), (4->2), (4->1), (3->2), (3->1), (2->1)

이런 식으로 연결시켜줘야 한다.

상대적인 순위 변경은 이러한 연결들을 반대로 적용해주면 된다.

이후에는 위상정렬을 돌려서 깔끔하게 찾을 수 있다.

 

코드는 깃허브!

github.com/onaeonae1/ProblemSovling/blob/master/BOJ%203665.cpp

onaeonae1/ProblemSovling

*이 문제를 기점으로 solved.ac 기준 골드1을 달성했다