Search

'분류 전체보기'에 해당되는 글 142건

  1. 2019.12.17 백준 1516 - 게임 개발

백준 1516 - 게임 개발

it/알고리즘 2019. 12. 17. 23:06 Posted by 하얀나다

 

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.Scanner;
 
public class Main {
 
    static ArrayList<Integer>[] aList;
    static int indegree[];
    static int N;
    static boolean T = true;
    static int[] time;
    static int[] getTime;
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        aList = new ArrayList[N + 1];
        indegree = new int[N + 1];
        time = new int[N + 1];
        getTime = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
            aList[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= N; i++) {
            T = true;
            int sec = sc.nextInt();
 
            time[i] = sec;
            while (T) {
                int a = sc.nextInt();
                if (a == -1) {
                    T = false;
                } else {
                    aList[i].add(a);
                    indegree[a]++;
                }
            }
        }
 
        result();
 
        sc.close();
 
    }
 
    private static void result() {
        Queue<Integer> que = new LinkedList<Integer>();
        Stack<Integer> s = new Stack<Integer>();
 
        for (int i = 1; i < aList.length; i++) {
            if (indegree[i] == 0) {
                que.offer(i);
            }
        }
 
        while (!que.isEmpty()) {
            int q = que.poll();
 
            s.push(q);
 
            for (int i = 0; i < aList[q].size(); i++) {
                int getaList = aList[q].get(i);
                indegree[getaList]--;
 
                if (indegree[getaList] == 0) {
                    que.offer(getaList);
                }
            }
        }
 
        while (!s.isEmpty()) {
            int spop = s.pop();
 
            getTime[spop] = ((aList[spop].size() == 0) ? time[spop] : time[spop] + maxs(spop));
        }
 
        for(int i = 1; i<getTime.length; i++) { 
            System.out.println(getTime[i]); 
        } 
    }
 
    private static int maxs(int a) {
 
        int max = 0;
        
        for (int i = 0; i < aList[a].size(); i++) {
            
            int b = aList[a].get(i);
            
            max = Math.max(max, getTime[b]);
        }
        
 
        return max;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  

 

'it > 알고리즘' 카테고리의 다른 글

백준 1735 - 분수 합  (0) 2019.12.17
백준 1260 - DFS와 BFS  (0) 2019.12.17
백준 1110 - 더하기 사이클  (0) 2019.12.17
백준 1058 - 친구  (0) 2019.12.17
백준 1012 - 유기농 배추  (0) 2019.12.17
 

티스토리툴바