위상 정렬

[백준] 1948. 임계경로 (Java)

문제 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 알고리즘 그래프, 위상 정렬 풀이 위상 정렬을 통해 마지막 노드까지 가는데 걸리는 시간의 최댓값을 구하고, 해당 최댓값을 만드는 경로에 있는 간선의 수를 출력하는 문제이다. 크기가 n를 배열을 만들어 각 도시까지 가는 최댓값을 저장한다. 이를 이용해 다음 도시로 가는데 걸리는 최댓값을 알 수 있다. 예제 입력 1로 표현하면 다음과 같다. 최댓값을 구했다면 이제 최댓값을 만드는 경로를 찾아야하는데 이는 도착 도시에서부터 역추적한다...

[백준] 1766. 문제집 (Java)

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 알고리즘 위상 정렬, 우선순위 큐 풀이 먼저 푸는 것이 좋은 문제는 반드시 먼저 풀어야한다는 조건이 있다. 즉 문제 사이에 순서가 있으므로 위상 정렬을 사용한다. 또한 각 문제는 쉬운 문제(번호가 작은 문제)부터 풀어야하므로 우선순위 큐를 사용하여 정렬을 유지하면서 큐에서 삭제되는 순서대로 값을 출력하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; imp..

[백준] 2056. 작업 (Java)

🔒 문제 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 🔑 알고리즘 다이나믹 프로그래밍(DP), 위상 정렬 💡 풀이 작업에 선행 관계가 있고, "K번 작업의 선행 작업은 1에서 K-1번 사이", 즉 사이클이 없다는 조건이 있으므로 위상 정렬을 이용하였다. 각 작업에 걸리는 시간을 배열에 저장하고 입력으로 그래프를 생성 후 진입 차수가 0인 작업(선행 작업이 없는 작업)을 큐에 삽입한다. 그리고 위상 정렬을 진행한다. - 1. 큐에서 꺼낸 작업은 작업이 끝난 셈으로 해당 작업을 선행 작업으로 필요로 ..

[백준] 2637. 장난감 조립 (Java)

🔒 문제 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 🔑 알고리즘 위상 정렬 💡 풀이 하나의 작은 부품이 여러 큰 부품에 들어간다면 작은 부품의 개수는 큰 부품이 각각 몇 개 필요한지 알아야 알 수 있다. 두 중간 부품이 서로를 필요로 하는 경우는 없다 = 사이클이 없다는 조건이 있다. 따라서 제일 큰 부품, 즉 완제품에서 기본 부품 방향으로. 만들어야하는 제품의 개수가 정해지면 ( 진입 차수가 0이 되면 ) 해당 제품을 만들 수 있는 하위 제품의 개수를 세는 식으로 위상 정렬을..

[백준] 2252. 줄 세우기 (Java)

🔒 문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🔑 알고리즘 위상 정렬 💡 풀이 특정 학생마다 다른 학생 앞에 서야 한다는 순서가 있고 키의 특성 상 사이클이 생기지 않기 때문에 위상 정렬을 사용할 수 있다. 특별한 것 없는 기본적인 위상 정렬 문제로 입력에 따라 그래프로 연결해주고, 뒤에 서야하는 학생의 진입 차수를 1 늘려준다. 입력이 끝나면 진입 차수가 0인 학생이 맨 앞에 서는 학생이므로 출력 후 큐에 넣고 위상 정렬을 진행한다. 위상 정렬은 큐가 빌..

[백준] 2623. 음악프로그램 (Java)

🔒 문제 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 🔑 알고리즘 위상 정렬 💡 풀이 보조 PD마다 생각한 가수의 순서가 정해져있으므로 위상정렬을 이용한다. 각 순서가 제시한 순서를 탐색하며 첫번째가 아닌 가수들의 번호의 진입차수를 1씩 늘린다. 또 앞의 원소와 뒤의 원소를 그래프로 연결한다. 예를 들어, 1 4 3 이라는 순서가 있다면 1->4 , 4->3을 그래프로 연결한다. for (int j = 1; j < num; j++) { int after = Integer.parseInt..

[백준] 21276. 계보 복원가 호석 (Java)

🔒 문제 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 🔑 알고리즘 위상 정렬, 해시맵, 정렬 💡 풀이 조상과 자손이라는 정해진 순서가 있고 사이클이 없고, 방향 그래프이므로 위상 정렬을 사용하였다. 이름을 리스트에 저장하고 정렬한다. 정렬한 순서대로 인덱스를 부여하고 이름을 Key, 인덱스를 Value로 하여 HashMap에 삽입한다. 조상과 자손의 정보가 주어지면 그래프에 연결하고 자손의 진입 차수를 1 늘린다. 진입 차수가 0이면 조상이 없음을 의미하므로 시조 리스트에 넣고 위상 정렬 큐에 ..

[백준] 1005. ACM Craft (Java)

🔒 문제 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 🔑 알고리즘 위상 정렬 💡 풀이 건물마다 짓는 순서가 있는, 사이클이 없는 유향 그래프이므로 위상 정렬을 이용했다. 이때, 건물마다 건설 시간이 달라서 예제의 4번 건물처럼 사전에 지어져야 하는 건물이 2개 이상인 경우 마지막 건물이 완성되는 시간 이후에 해당 건물을 지을 수 있다. 예를 들어 2번 건물이 11초에 지어지지만 3번 건물이 110초에 지어져서 4번 건물의 건설은 11초가 아닌 110초부터 시작된다. 이를 위해서 다음 노드를 탐색할 때..