https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
분류 : 위상 정렬
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class Myscanner {
BufferedReader br;
StringTokenizer st;
public Myscanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
public static Myscanner sc = new Myscanner();
public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static void main(String[] args) throws IOException {
int TC = sc.nextInt();
while (TC-- > 0) {
int N = sc.nextInt();
int M = sc.nextInt();
int[] Time = new int[N+1];
int[] idg = new int[N+1];
int[] result = new int[N+1];
Vector<Integer>[] Vector = (Vector<Integer>[]) new Vector[N+1];
PriorityQueue<se> q = new PriorityQueue<>();
for (int i = 1; i <= N; i++) {
Vector[i] = new Vector<Integer>();
}
for (int i = 1; i <= N; i++) {
Time[i] = sc.nextInt();
}
for (int i = 0; i < M; i++) {
int X = sc.nextInt();
int Y = sc.nextInt();
Vector[X].add(Y);
idg[Y]++;
}
int W = sc.nextInt();
for (int i = 1; i <=N; i++) {
if (idg[i] == 0) {
result[i] = Time[i];
q.offer(new se(i));
}
}
for (int i = 1; i <= N; i++) {
se s = q.poll();
int curr = s.s;
for (int next : Vector[curr]) {
result[next] = Math.max(result[next], result[curr] + Time[next]);
if (--idg[next] == 0)
q.offer(new se(next));
}
}
out.println(result[W] + " ");
}
out.flush();
}
}
class se implements Comparable<se> {
int s;
se(int s) {
this.s = s;
}
@Override
public int compareTo(se o) {
return s <= o.s ? -1 : 1;
}
}
1005번 문제. 항상 보면서 이건 어떻게 풀까 하다가 도전도 안 하고 포기한 문제.
그러다 이번에 종 만북 깊이 우선 탐색 부분을 공부하면서 위상 정렬에 대해서 배웠다.
단순히 책만으로는 이해가 되지 않아서 검색을 통해 코드를 많이 봤고 아무래도 위상 정렬 문제는 정형화된 코드가 있는 거 같다.
Vector, List, ArrayList 3가지를 이용해서 제출해봤는데 Vector가 메모리도 적고 시간도 좀 더 빠르게 나왔고
물론 내 코드보다 더 빠르게 하는 방법도 있겠지만 아직은 잘 모르겠다
'PS' 카테고리의 다른 글
[BOJ]1600번 : 말이 되고픈 원숭이 (0) | 2017.04.14 |
---|---|
[BOJ]9373번 : 복도 뚫기 (0) | 2017.04.06 |
[BOJ]10422번 : 괄호 (0) | 2017.04.03 |
[BOJ]11723번 : 집합 (0) | 2017.04.03 |
[BOJ]2206번 : 벽 부수고 이동하기 (0) | 2017.04.02 |