위상정렬4 [백준] BOJ1766 - 문제집 문제 출처 https://www.acmicpc.net/problem/1766 해당 문제는 위상정렬을 이용하여 풀 수 있는 문제. 문제간에는 우선순위가 있어서 먼저 푸는것이 좋은 문제의 경우 먼저 풀어야(방문) 한다. 단, 풀 수 있는 문제가 여러개인 경우 (indegree가 0 인 문제가 여러개인 경우) 문제 번호가 낮은 것이 더 쉬운 문제이므로 먼저 풀어야(방문) 한다. // 위상정렬 4 // Priority Queue 사용 import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; imp.. 2018. 9. 9. [백준] BOJ1516 - 게임 개발 위상정렬을 이용해 풀 수 있는 문제 건물을 짓기 위해 다른 건물을 먼저 지어야 하는 경우가 있다고 했기 때문에,가장 처음에 지을 수 있는 건물(indegree가 0인 건물) 부터 지을 수 있다. 그래서, 위상정렬을 이용하면 쉽게 풀리는 문제 import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class Main { public static void main(String[] args.. 2018. 9. 9. [백준] BOJ2252 - 줄 세우기 위상정렬 알고리즘을 이용하여 풀 수 있는 간단한 문제 import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception{//System.setIn(new FileInputStream("src/input.txt"));BufferedReader br = new BufferedR.. 2018. 9. 9. [백준] BOJ3665 - 최종순위 문제 https://www.acmicpc.net/problem/3665 풀이 2가지 방법으로 풀이 가능하다.(1) indegree 가 저장된 2차원 배열을 Sort하는 방법-> 이 방법이 가능한 이유는, indegree가 순위 정보를 나타내기 때문에 무조건 1씩 증가하는 형태를 보일 수 밖에 없다. indegree 값이 1씩 증가하지 않는 경우, 순위 정보가 잘못된 것!!(2) queue 를 이용한 위상정렬 (1) indegree 가 저장된 2차원 배열을 Sort하는 방법import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.Arrays;import java.ut.. 2018. 5. 13. 이전 1 다음