[BOJ 2252]

문제 바로가기 : https://www.acmicpc.net/problem/2252
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

topology sort

나동빈님의 글을 참고했고 큰 도움이 됐습니다. 감사합니다.

정렬이라고 하면 내림차순, 오름차순으로 정리하는걸 떠올리기 쉽지만 또 다른 조건으로 정리할 수도 있다.
어떤 이벤트들에 대해서 설정해 놓은 순서가 있고 이를 기준으로 정렬을 해야 한다면 위상 정렬(Topology Sort)을 사용하면 된다.
특정 노드가 다른 노드에 대해서 연결이 돼있는 개수를 진입 차수라고 하며 진입 차수가 0인 노드부터 큐에 넣어준다.
큐에 들어간 노드를 앞에서부터 꺼내면서 출력해주고, 해당 노드의 간선들을 모두 제거해준다.
동시에 진입 차수를 업데이트 해주는데 진입 차수가 0인 노드가 있다면 큐에 넣어준다. 이를 큐가 빌 때까지 반복한다.

review

참고한 글에서 설명이 매우 자세하게 돼있기도 하고 알고리즘 자체가 어렵지 않아서 금방 구현할 수 있었다.
위상 정렬의 개념이 문제에서 별도의 수정없이 진행되는 걸로 보아서 기본 문제에 속하는 듯하다.