반응형
위상정렬 (Topological Sort) 의 가장 대표적인 문제
위상정렬을 처음 이해하고 문제를 푸는데 어려웠다. 머리속에 문제를 이해는 했는데 코드는 잘 안짜지는 느낌?
풀이
1. 값을 저장해준다. List를 이용하여.
2. indegree가 0인 값을 큐에 모두 집어 넣는다.
3. 큐가 빌때까지 0인 값을 하나씩 빼서 그 다음 값을 다시 큐에 집어 넣는다. (단 그때 화살표 값인 Indegree를 하나씩 줄인다.)
4. 끝
의 과정 반복이다.
문제가 안풀리면 위상정렬을 공부하고 다시 보면 될것이다.
맞다. 이문제는 PriorityQueue를 사용해야한다. 왜냐하면 Queue에 같이 들어있을 때, 쉬운문제(번호가 작은 순)으로 풀어야 하기 때문
Queue를 사용하면 선입선출이기 때문에 값이 다르게 나온다.
소스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | import java.io.FileInputStream; import java.util.ArrayList; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(new FileInputStream("input.txt")); int N = sc.nextInt(); int M = sc.nextInt(); int[] indegree = new int[N+1]; ArrayList<Integer>[] list = new ArrayList[N+1]; //LinkedList 사용해도 상관 없음 for(int i=1; i<=N; i++){ list[i] = new ArrayList<Integer>(); } for(int i=0; i<M; i++){ int x = sc.nextInt(); int y = sc.nextInt(); list[x].add(y); //리스트 안의 리스트에 값을 넣어준다. indegree[y]++; //자신을 가르키고 있는 화살표의 갯수 } PriorityQueue<Integer> q = new PriorityQueue<Integer>(); for(int i=1; i<=N; i++){ //indegree가 0인 값들 모두 큐에 넣어준다. if(indegree[i]==0){ q.add(i); } } while(!q.isEmpty()){ //indgree가 0인 값을 큐에서 뽑는다. int current = q.poll(); System.out.print(current+" "); //뽑힌 곳에서 갈 수 있는 곳들을 검색하여 indegree를 -1한다.(자신을 가르키는 화살표가 하나 사라졌기 때문에) for(int i=0; i<list[current].size(); i++){ int next = list[current].get(i); indegree[next]--; //indegree가 0이라면 큐에 넣는다. if(indegree[next]==0){ q.add(next); } } } } } | cs |
반응형
'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글
| [BOJ] 백준 1516 - 게임 개발 (자바) (0) | 2018.02.06 |
|---|---|
| [BOJ] 백준 2252- 줄 세우기 (자바) (0) | 2018.02.06 |
| [BOJ] 백준 1267 - 핸드폰 요금 (자바) (0) | 2018.02.05 |
| [BOJ] 백준 1697 - 숨바꼭질 (자바) (0) | 2018.02.05 |
| [BOJ] 백준 2979 - 트럭 주차 (자바) (0) | 2018.02.03 |
