본문 바로가기

위상정렬2

[BOJ][1516] 게임 개발 문제 : https://www.acmicpc.net/problem/1516 전형적인 위상정렬 문제.입력값들로 위상 정렬을 위한 그래프를 먼저 만든다.건물의 cost 정보를 배열에 따로 저장해둔다. 큐를 하나 만들어서 우선시 개발되어야 하는 건물들이 없는 건물 인덱스를 모두 넣는다.큐에 들어갈 때 각 건물이 완성되기까지 걸리는 최소 시간이 정해진다.처음 큐에 값을 세팅할 때는 자기 자신이 만들어지는데 걸리는 시간이 각 건물이 완성되기까지 걸리는 최소 시간이 된다. 큐를 pop하면서 가져온 인덱스 건물(A)과 앞서 만든 그래프에서 간선을 가지고 있는 건물(B)에서 해당 간선 (A -> B)을 제거한다.간선이 있다는 뜻은 B 건물을 만드는데 A 건물이 우선시되어 만들어져야 한다는 의미이다.따라서 B 건물을 만.. 2019. 1. 20.
[BOJ][3665] 최종 순위 문제 : https://www.acmicpc.net/problem/3665 위상정렬 문제다.등수가 3등인 사람은 1, 2등이 정해지는 경우 3등이 정해진다.이를 그래프로 나타내면 위와 같다. 1등은 앞에 아무도 없는 경우 1등이다.2등은 1등이 정해져서 화살표가 없어지면 2등 앞의 등수가 아무도 없게되고 2등이 정해진다.3등도 마찬가지로 1, 2등이 정해지면 3등이 정해진다. m개 등수가 바뀌는 쌍이 주어지면 2개 화살표를 반대로 바꾼다.만약 m이 2이고 (1,2), (2,3)이 입력값으로 주어지면 위 그림과 같이 화살표가 바뀐다.이때, 1, 2, 3 사이에는 싸이클이 생겨서 1등을 정할 수 없게 되서 IMPOSSIBLE을 출력한다.모든 등수 뿐만 아니라 2개 이상의 등수 사이에 위와 같이 싸이클이 발생.. 2019. 1. 19.