[백준/JAVA] 1516번: 게임 개발
🔺 문제
1516번: 게임 개발
첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부
www.acmicpc.net
🔺 코드
|
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
|
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]);
}
}
}
|
cs |
✅ 해결 아이디어
✔ 위상 정렬 - BFS
💥 유의사항
⇨ 필요한 것
1) 건물 생산 시간 배열 (int[] time)
2) 진입 차수 배열 (int[] degree)
3) 정답 배열 (int[] result)
⇨ 시간 업데이트
: Math.max(현재 건물(노드)에 저장된 값, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간)
🔺 다른 풀이들
- 인접 배열 사용 & 가장 깔끔한 설명 굿
[백준/자바] 1516 게임 개발
문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있
settembre.tistory.com
- 과정 설명 굿!!!!
백준 1516번 : 게임 개발 java
이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간
dy-coding.tistory.com
- 우선순위 큐 활용한 방법도 적어두심!
[BOJ] 백준 1516번 : 게임 개발 (JAVA)
문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있
steady-coding.tistory.com
- dfs와 dp를 사용하심
BOJ - 게임 개발 1516번 (JAVA)
❓ 문제 - 백준 게임 개발 1516번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/1516) 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리
developer-ellen.tistory.com
💬 느낀 점
위상 정렬,,,,을 바로 생각해낼 수 있을까..?라는 생각이 들지만
더 많이 풀어봐야겠지!
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 6/23 |
(+ 6/23 2회독)
건물 생산 시간 배열과, 정답 결과 배열 만드는 것을 놓치다...
|
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
|
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);
}
}
|
cs |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편