기록방

👉 문제링크 🔸 문제 분석 🔸N개의 도시 사이 M개의 도로가 주어진다. 각 도로를 건너는 시간이 있고, 출발지와 도착지가 주어진다.도로는 출발지부터 도착지까지 단방향 비순환 그래프이다.많은 경로 중에 가장 늦게 도착하는 경로에서 지나는 도로의 수 총합을 출력한다.🔸 문제 풀이 🔸출발지부터 도착지까지 단방향 비순환 그래프이므로, 위상 정렬(Topology Sort)을 통해 최대값을 구할 수 있다.건너온 경로의 수를 카운트 해야하므로 역방향 탐색이 필요하다.1분도 쉬지 않고 달린 경로이므로 현재 시간과 도로의 소요 시간의 차이가 맞아 떨어져야 한다.경로를 중복되게 체크하지 않기 위해서 도시를 방문처리 한다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque..

👉 문제링크🔸 문제 분석 🔸스타크레프트 같은 게임에서 각 건물을 짓는데 필요한 최소 시간을 구해보자.N개의 건물 별 짓는 시간과 먼저 지어져야 하는 건물의 번호가 주어진다.🔸 문제 풀이 🔸선행 되어야 하는 번호가 주어지므로 위상 정렬(Topology Sort)을 활용해 풀이할 수 있다.선행 건물 건설 직후 해당 건물을 짓는데, 선행 건물이 여러개일 경우 순서를 정할 수 없다.따라서 선행 건물이 지어지는 시간의 최대값 + 현재 건물을 짓는 시간을 구한다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Queue;import java.util.StringTokenizer;pu..

👉 문제링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 🔸 문제 분석 🔸 앞선 건물들이 모두 지어져야 해당 건물을 지을 수 있게 되는 건물 순서 규칙이 존재한다. 건물은 동시에 여러 개를 지을 수 있다. 목표 건물을 짓는데 드는 최소 시간을 출력한다. 🔸 문제 풀이 🔸 건물이 지어지는 순서가 달라질 수 있는데 선행 작업이 존재하므로, 위상 정렬을 사용해서 풀이한다. 동시에 건물을 지었다고 할 때, 가장 오래 걸리는 건설 시간이 최소값이다. 따라서 최대값을 갱신해서 저장하기 위해 DP를 사용한다. 점..

👉 문제링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🔸 문제 분석 🔸 N명의 학생들을 키 순서대로 줄을 세운다. 모두의 키 정보가 주어지는 것이 아니라, 두 학생을 비교해서 누가 앞에 오는지에 대한 정보만 주어진다. 위상 정렬 알고리즘에 대한 간단한 문제이다. 키가 큰 학생이 앞에 오는지, 작은 학생이 앞에 오는지에 대한 정보는 없고, 누가 앞으로 오느냐만 주어진다. 따라서 답이 여러가지가 될 수 있으므로 서브테스크 문제이다. BFS로 간단히 풀이할 수 있다..