음.. 처음에 문제를 보고 난해했다.
그런데 조금 검색해보면서 확인해보니 위상정렬이나 DP로 풀 수 있다는걸 알고,
생각을 좀 해봤다.
일단 그래프인건 확실하고, 중등부여서 데이터도 적고 하니 DP로 풀자 생각했다.
DAG여서 1에서 끊어줘야되고, 시간초과가 나니까 Memorization도 해줘야 됐다.
그리고 순서를 표시하기 위해 disjoint-set도 했다. (트리구조로 parent를 찾아감)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.util.*; | |
| /** | |
| * BOJ 2611 자동차경주 | |
| * https://gist.github.com/KSH-code/6ef723e29a1cffa75f4a429984047cd7 | |
| */ | |
| class Edge{ | |
| public int V,W; | |
| public Edge(int v, int w){ | |
| V = v; | |
| W = w; | |
| } | |
| } | |
| public class Main{ | |
| private static int V[]; | |
| private static int MAX[]; | |
| private static ArrayList<Edge> E[]; | |
| public static void main(String[] args) throws IOException{ | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| int N = Integer.parseInt(br.readLine()); | |
| int M = Integer.parseInt(br.readLine()); | |
| V = new int[N+1]; | |
| E = new ArrayList[N+1]; | |
| MAX = new int[N+1]; | |
| for(int i = 1; i<=N; i++){ | |
| E[i] = new ArrayList<>(); | |
| } | |
| for(int i = 0; i<M; i++){ | |
| String str1[] = br.readLine().split(" "); | |
| int s = Integer.parseInt(str1[0]); | |
| int e = Integer.parseInt(str1[1]); | |
| int w = Integer.parseInt(str1[2]); | |
| E[s].add(new Edge(e, w)); | |
| } | |
| System.out.println(checkWeight(1, 0)); | |
| printTree(1); | |
| } | |
| public static int checkWeight(int v, int w) { | |
| LinkedList<Edge> e = new LinkedList<>(); | |
| int max = 0; | |
| int tempWeight = 0; | |
| if(MAX[v] > 0){ | |
| max = MAX[v]; | |
| }else if(E[v].size() > 0){ | |
| for(int i = 0; i<E[v].size(); i++){ | |
| e.add(E[v].get(i)); | |
| } | |
| if(v == 1) E[v].clear(); | |
| while(!e.isEmpty()){ | |
| Edge temp = e.remove(); | |
| tempWeight = checkWeight(temp.V, temp.W); | |
| if(tempWeight > max){ | |
| V[v] = temp.V; | |
| max = tempWeight; | |
| } | |
| } | |
| MAX[v] = max; | |
| } | |
| return w + max; | |
| } | |
| private static void printTree(int i){ | |
| if(V[i] == 1){ | |
| System.out.print(i + " "); | |
| System.out.print(1); | |
| }else{ | |
| System.out.print(i + " "); | |
| printTree(V[i]); | |
| } | |
| } | |
| } |
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번) (0) | 2017.10.23 |
|---|---|
| BOJ 12852 1로 만들기 2 풀이 (0) | 2017.10.20 |
| BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선) (0) | 2017.10.19 |
| BOJ 11657 타임머신 풀이 벨만 포드 (0) | 2017.10.19 |
| BOJ 14852 타일채우기 3 풀이 (0) | 2017.10.18 |