[백준/JAVA] 1516번: 게임 개발

🔺 문제

1516번: 게임 개발

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        ArrayList<ArrayList<Integer>> A = new ArrayList<>();   
        for(int i = 0 ; i <= N ; i++) {
            A.add(new ArrayList<>());
        }
        
        int[] indegree = new int[N + 1];    // 진입 차수 배열
        int[] time = new int[N + 1];     // 건물 생산 시간
        
        for(int i = 1 ; i <= N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            
            // 인접 리스트 초기화
            while(true) {
                int preTemp = Integer.parseInt(st.nextToken());
                if(preTemp == -1) break;
                A.get(preTemp).add(i);
                indegree[i]++;
            }
        }
        
        
        // 위상 정렬
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1 ; i <= N ; i++) {
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] result = new int[N + 1];  // 정답 리스트
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : A.get(now)) {
                indegree[next]--;
                
                // 시간 업데이트 : Math.max(현재 저장된 값, 현재 출발 노드 + 비용)
                result[next] = Math.max(result[next], result[now] + time[now]);
                
                if(indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
 
        for(int i = 1 ; i <= N ; i++) {
            System.out.println(result[i] + time[i]);
        }
    }
}

✅ 해결 아이디어
✔ 위상 정렬 - BFS

 

💥 유의사항

⇨ 필요한 것

1) 건물 생산 시간 배열 (int[] time)

2) 진입 차수 배열 (int[] degree)

3) 정답 배열 (int[] result)

 

⇨ 시간 업데이트

: Math.max(현재 건물(노드)에 저장된 값, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간)

 

---

🔺 다른 풀이들

- 인접 배열 사용 & 가장 깔끔한 설명 굿

[백준/자바] 1516 게임 개발

 

 

- 과정 설명 굿!!!!

백준 1516번 : 게임 개발 java

 

 

- 우선순위 큐 활용한 방법도 적어두심!

[BOJ] 백준 1516번 : 게임 개발 (JAVA)

 

 

- dfs와 dp를 사용하심

BOJ - 게임 개발 1516번 (JAVA)

---

💬 느낀 점

위상 정렬,,,,을 바로 생각해낼 수 있을까..?라는 생각이 들지만

더 많이 풀어봐야겠지!

 

 

1회독	2회독	3회독	4회독	5회독
V	6/23

 

 

(+ 6/23 2회독)

건물 생산 시간 배열과, 정답 결과 배열 만드는 것을 놓치다...

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        
        ArrayList<Integer>[] A = new ArrayList[N + 1];  // 인접 리스트
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        int[] indegree = new int[N + 1];    // 진입 차수 배열
        int[] time = new int[N + 1];        // 🎈 건물 생산 시간 🎈
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            time[i] = Integer.parseInt(st.nextToken());
            
            while(true) {
                int idx = Integer.parseInt(st.nextToken());
                if(idx == -1)   break;
                A[idx].add(i);
                indegree[i]++;
            }
        }
        
        // 위상 정렬
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1 ; i <= N ; i++) {
            if(indegree[i] == 0) {
                queue.add(i);
            }
        }
        
        int[] result = new int[N + 1];  // 정답 리스트
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(int next : A[now]) {
                indegree[next]--;
                
                // 🔔 시간 업데이트 : Math.max(현재 저장된 값, 현재 출발 노드 + 비용) 🔔
                result[next] = Math.max(result[next], result[now] + time[now]);
                
                if(indegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
        for(int i = 1 ; i <= N ; i++) {
            sb.append(result[i] + time[i]).append("\n");
        }
        System.out.println(sb);
    }
}
 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편