백준 1005. ACM Craft

티스토리 뷰

tose33 2022. 7. 14. 15:26

1005번: ACM Craft

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부

www.acmicpc.net

위상정렬 (topology sort) 문제다.

위상 정렬 (Topology sort)

토폴로지(영어: topology, 문화어: 망구성방식)는 컴퓨터 네트워크의 요소들(링크, 노드 등)을 물리적으로 연결해 놓은 것, 또는 그 연결 방식을 말한다. https://m.blog.naver.com/ndb796/221236874984 25...

tose33.tistory.com

솔직히 위상 정렬에 대해서 완전 까맣게 잊고 있어서 오래걸렸다 ..

위상 정렬 알고리즘만 알면 쉬운 문제다.

위상 정렬은 순서가 정해져있는 작업을 순서대로 수행할때 그 순서를 정해준다.

이 문제는 특정 건물 W를 건설하는 순서를 정해주면 된다.

어떤 건물을 건설할수 있는 조건이 여러개라면 그 모든 조건을 달성한 후에야 건설할수 있기 때문에, 해당 건물을 짓기 까지 걸리는 여러 시간들중 가장 큰 시간을 선택해야한다.

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함