위상 정렬8 [백준] 21276번 - 계보 복원가 호석 [Java] https://www.acmicpc.net/problem/21276 1. 아이디어 이름을 통해 처리하는 상황이 많아서 Set, Map 등 다양한 자료구조를 활용했고 시조부터 위상 정렬을 수행해서 해결했다.2. 문제풀이 자식, 자손, 진입차수를 Map 자료구조로 처리했다. 자식은 출력을 위해 TreeMap을 활용했고 value도 TreeSet으로 미리 정렬하도록 했다. 자식과 자손을 구부하는게 포인트인데 위상 정렬은 자손으로 수행하며 선행 노드의 제거로 후행 노드의 진입차수가 0이 된 순간이 부모와 자식 관계가 됨을 활용했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] arg.. 2025. 2. 3. [백준] 2637번 - 장난감 조립 [Java] https://www.acmicpc.net/problem/2637 1. 아이디어 번호와 개수를 갖는 노드를 활용한 위상 정렬과 다이나믹 프로그래밍으로 해결할 수 있었다.2. 문제풀이 장난감의 개수를 간선의 가중치로 생각하는 방향 비순환 그래프에서 위상 정렬로 구현했다. 위상 정렬 과정에서는 카운팅 배열에 장난감 부품의 개수를 저장했는데 노드를 정렬할 때마다 후행 작업에 선행 작업의 개수를 전달하면 부품 수를 전달할 수 있다. 이후 진출차수 배열에서 0인 노드가 기본 부품임을 이용해서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { int v; .. 2025. 2. 3. [백준] 2056번 - 작업 [Java] https://www.acmicpc.net/problem/2056 1. 아이디어 위상 정렬과 작업 시간을 저장하는 다이나믹 프로그래밍을 활용하면 해결할 수 있다.2. 문제풀이 위상 정렬 과정에서 선행 작업이 없는 경우 해당 작업 시간을 선행 작업이 있는 경우 선행 작업을 하는데 걸리는 총 시간과 해당 작업을 하는데 걸리는 시간의 합과 현재까지 구한 해당 작업을 하는데 걸리는 총 시간 중 더 큰 값이 해당 작업을 하는데 걸리는 총 시간이 된다. 이를 통해 모든 작업이 각각 완료되는데 걸리는 총 시간을 배열로 구할 수 있었고 이 중 가장 큰 값이 모든 작업을 완료하는데 걸리는 총 시간이 됐다. N번 작업보다 번호가 작은 작업이 더 오래걸릴 수 있음에 주의해야한다.3. 코드 import java.io.*;i.. 2025. 2. 3. [백준] 2623번 - 음악프로그램 [Java] https://www.acmicpc.net/problem/2623 1. 아이디어 위상 정렬 활용하면 간단하게 해결할 수 있다.2. 문제풀이 위상 정렬을 구현만 하면 되는 문제로 입력 값으로 만든 그래프가 방향 비순환 그래프가 되지 않는 경우가 존재하는 문제다. 이를 해결하기 위해 정렬 시킨 노드의 개수를 세서 모든 노드가 정렬됐는지 판단하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy.. 2025. 2. 3. [백준] 1766번 - 문제집 [Java] https://www.acmicpc.net/problem/1766 1. 아이디어 위상 정렬과 우선순위 큐를 활용하면 해결할 수 있다.2. 문제풀이 위상 정렬만으로 조건 1과 조건 2는 만족할 수 있는데 조건 3이 안될 수가 있다. 위상 정렬의 Queue에 있는 원소들은 모두 동일한 단계이므로 Queue를 우선순위 큐로 바꾼 위상정렬을 적용하면 조건 3도 만족시킬 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR.. 2025. 2. 3. [백준] 1516번 - 게임 개발 [Java] https://www.acmicpc.net/problem/1516 1. 아이디어 위상 정렬과 건설 시간을 저장하는 다이나믹 프로그래밍을 활용하면 해결할 수 있다.2. 문제풀이 이전 ACM Craft 문제와 유사한 문제로 동일하게 접근했다.([코딩테스트 준비/백준] - [백준] 1005번 - ACM Craft [Java]) 각 건물의 건설 시간은 dist 배열에 저장했는데 dist 배열은 선행 건물이 없는 건물은 해당 건물의 건설시간으로 초기화하면 되고 선행 건물이 있는 경우 (선행 건물을 건설하는데 걸리는 총 시간 + 해당 건물을 건설하는데 걸리는 시간)과 현재까지 계산된 해당 건물을 건설하는데 걸리는 총 시간 중 큰 값이 해당 건물을 건설하는데 걸리는 총 시간이 된다.3. 코드 import java... 2025. 2. 3. [백준] 1005번 - ACM Craft [Java] https://www.acmicpc.net/problem/1005 1. 아이디어 위상 정렬과 건설 시간을 저장하는 다이나믹 프로그래밍을 활용하면 해결할 수 있다.2. 문제풀이 그림에서 위상 정렬의 힌트를 얻을 수 있어서 위상 정렬로 접근했다. 각 건물의 건설 시간은 dist 배열에 저장했는데 dist 배열은 선행 건물이 없는 건물은 해당 건물의 건설시간으로 초기화하면 되고 선행 건물이 있는 경우 (선행 건물을 건설하는데 걸리는 총 시간 + 해당 건물을 건설하는데 걸리는 시간)과 현재까지 계산된 해당 건물을 건설하는데 걸리는 총 시간 중 큰 값이 해당 건물을 건설하는데 걸리는 총 시간이 된다.3. 코드 import java.io.*;import java.util.*;public class Main { .. 2025. 2. 2. [백준] 2252번 - 줄 세우기 [Java] https://www.acmicpc.net/problem/2252 1. 아이디어 위상 정렬을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 키가 작은 친구에서 키가 큰 친구로 간선이 향하는 방향 비순환 그래프로 생각할 수 있으므로 위상 정렬을 구현했고 노드를 꺼내는 과정에서 StringBuilder에 담은 후 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 2. 2. 이전 1 다음
