방향 비순환 그래프4 [백준] 16169: 수행 시간 - JAVA https://www.acmicpc.net/problem/16169 풀이컴퓨터마다 계급이 있어서 i번 컴퓨터가 동작하기 위해서는 i-1번 컴퓨터들이 먼저 동작을 해야한다. 위상정렬을 이용해 구현했다. 컴퓨터들의 정보를 저장하고, 계급의 오름차순으로 i번과 i+1을 연결시키는 연결리스트로 저장했다. 위상정렬을 위한 배열도 저장하여 이 값이 0인 것부터 큐에 넣어 처리해주었다. 메모리: 14148KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Computer { int idx; int rank; int speed; public Compu.. 2024. 5. 19. [백준] 2637: 장난감 조립 - JAVA https://www.acmicpc.net/problem/2637 풀이X, Y, K가 주어지는데 X를 만드는데 부품 Y가 K개 필요하다는 뜻이다. 다른 부품으로 만들어지지 않는 기본 부품이 몇개씩 필요한지 구하는 문제이다. 완제품의 번호는 N으로 주어져있다. 따라서, N부터 탐색하면 된다. 위상정렬을 이용했는데 X를 만드는데 Y가 필요하다면 Y의 위상정렬 배열에 +1해줬다. N부터 시작하여 연결된 부품의 위상을 빼가면서 0이 되면 큐에 추가하는 식으로 구현했다. 메모리: 15960KB시간: 148ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int from; i.. 2024. 5. 17. [백준] 1005: ACM Craft - JAVA https://www.acmicpc.net/problem/1005 풀이위상정렬을 이용해 건물을 건설하는 시간을 구하는 문제. 어떤 건물을 짓기 위해 우선적으로 지어져야 할 건물이 있다. 특정 번호의 앞에 지어져야할 건물이 여러개가 있다면 그중 가장 오래걸리는 것이 끝난 후 지을 수 있게 된다. 따라서 걸리는 시간을 오름차순으로 하기 위해 우선순위큐를 이용했다. 목표한 건물에 도달했으면 시간을 출력하면 끝. 메모리: 245956KB시간: 864ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node implements Comparable { int num; int time; .. 2024. 5. 13. [백준] 1516: 게임 개발 - JAVA https://www.acmicpc.net/problem/1516 풀이위상 정렬을 이용하는 문제이다. 건물을 지을 때 먼저 지어야 할 건물이 정해져 있다. 즉, 먼저 지어야할 건물의 개수가 0이되면 지을 수 있는 것이다. 인접리스트로 건물을 지은 다음에 지을 수 있는 건물을 저장해놓는다. in_degree 배열에 먼저 지어야 할 건물의 개수를 저장한다. in_degree 배열이 0인 것부터 먼저 queue에 넣고 탐색하여 인접리스트에서 다음 건물의 in_degree값을 하나 빼준다. in_degree 값이 0이되면 queue에 넣는다. 메모리: 21612KB시간: 260ms언어: Java 11import java.io.*;import java.util.*;public class Main { pub.. 2024. 5. 13. 이전 1 다음