반응형 백준/그래프3 백준 2056. 작업 🅰 백준 2056. 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net ✏️ 문제 풀이 순서가 주어지므로 위상정렬의 개념을 이용하여서 풀었다. 일단 위상정렬이랑 비슷하지만 선행관계가 없는 작업들은 동시에 수행되기 때문에 이 부분을 생각해내는데 시간이 조금 걸렸다. pq에 저장되는 정점들은 comparable을 이용하여 수행시간이 작은 순으로 정렬을 시켜서 하나씩 뽑아낸다. pq에는 들어오는 간선이 없는 정점부터 저장을 해서 탐색을 시작한다. cur = pq.poll() 한 정점이 걸리는 시간을 an.. 2021. 9. 29. 백준 1766. 문제집 🅰 백준 1766. 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ✏️ 문제 풀이 백준 2252 줄 세우기 문제랑 99% 동일한 문제이다. 다른점이란 가능하면 쉬운 문제를 먼저 풀어야 한다는 조건이 하나 더 생겼을 뿐이다. 이를 해결하기 위해서는 queue대신 PriorityQueue를 사용하여 들어오는 정점들을 오름차순으로 저장해서 순서대로 탐색하면 된다는 점이다. 아래에는 2252 줄 세우기 문제랑 해설이 동일하다. 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것.. 2021. 9. 28. 백준 2252. 줄 세우기 🅰 백준 2252. 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ✏️ 문제 풀이 위상정렬의 개념을 이용해서 풀면 쉽게 풀리는 문제이다. 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것으로, 어떤 일을 하는 순서를 찾는 알고리즘이다. 중요한 것은 큐에 넣을 때 연결된 간선이 하나밖에 없는 정점만 넣어줘야 한다는 것이다. 먼저 인접리스트, 큐, 연결된 간선 수를 체크해줄 check배열을 선언하였다. 먼저 그래프를 생성하기 위해 인접리스트를 생성해주고, .. 2021. 9. 28. 이전 1 다음
