[문제]
숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.
게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.
편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.
[입력]
첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. 모든 건물을 짓는 것이 가능한 입력만 주어진다.
[출력]
N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.
[예제]
| 예제 입력1 | 예제 출력1 |
| 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 |
10 20 14 18 17 |
>문제 풀이
위상정렬 문제였는데, 이론을 배우긴 했는데 문제로 풀어보는건 처음이라 다른 블로그의 코드를 참고하여 공부하였습니다.
문제 조건
1. 어떤 건물을 짓기 위해 다른 건물을 먼저 지어야 할 수도 있다.
2. 여러 건물을 동시에 지을 수 있다.
순환이(cycle) 없고 상대적 순서를 지켜서 수행해야 한다. -> 위상정렬 (Topological Sort)
inDegree: 선행건물들의 개수가 0인 애들을 큐에 넣어서 실행시간을 넣어놓고 이 건물을 선행 조건으로 하는 건물들을 살펴봐야한다.
선행 건물들 부터 실행시간을(여기서 말한 실행시간은 선행조건을 포함한 건설시간) 저장해놓고 다음 건물을 지어야 함으로 dp적인 요소가 들어갔다고 할 수 있다.(Memoization)
나도 다른 분의 코드와 설명을 참고하여 공부했기 때문에 이상 자세한 설명은 생략한다.
(세부적인 내용은 아래 블로그를 참고하길 바랍니다.)
https://subbak2.tistory.com/53
[BOJ 백준] 게임 개발(1516) Java
링크 : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야
subbak2.tistory.com
>전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N;
static Building[] buildingList;
static int input;
static Queue<Integer> queue;
static StringBuilder sb= new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
//1.입력
N= Integer.parseInt(br.readLine());
buildingList= new Building[N+1];
for(int i=1; i<=N; i++{
buildingList[i]= new Building();
}
//2. N개의 건물정보 입력
for(int i=1; i<=N; i++) {
st= new StringTokenizer(br.readLine());
buildingList[i].time= Integer.parseInt(st.nextToken());
input= Integer.parseInt(st.nextToken());
while(input!=-1) {
buildingList[i].inDegree++;
buildingList[input].adjList.add(i);
input= Integer.parseInt(st.nextToken());
}
}
//2. 위상정렬 재료 만들기
//- 선행건물이 없는 경우(inDegree=0)인 경우 큐에 넣기
queue= new ArrayDeque<Integer>();
for(int i=1; i<=N; i++) {
if(buildingList[i].inDegree==0) {
queue.add(i);
}
}
//3. 위상정렬
while(!queue.isEmpty()) {
//1) 선행건물이 더이상 없는 녀석을 뽑아서 최종 건설시간에 자기 자신을 더해줌
int quePoll= queue.poll();
buildingList[quePoll].result+= buildingList[quePoll].time;
//2) 자신을 지어야 지을 수 있는 건물들에게 선행건물의 건설이 끝났음을 알림
for(int i: buildingList[quePoll].adjList) {
//2-1) 선행건물의 개수 빼주기
buildingList[i].inDegree--;
//2-2) 타겟건물은 아직 건물을 지을 수 없는 상태
//->현재 상태에서 타겟 건물의 res는 선행건물의 건설시간 중 최댓값: res를 최댓값으로 갱신시켜야
buildingList[i].result= Math.max(buildingList[i].result, buildingList[quePoll].result);
//2-3) 타겟건물의 선행건물 개수가 0이면 큐에 넣기
if(buildingList[i].inDegree==0) queue.add(i);
}
}
for(int i=1; i<=N; i++) {
sb.append(buildingList[i].result+"\n");
}
System.out.println(sb.toString());
}//main
public static class Building{
int time; //각 건물 건설시간
int inDegree; //건물의 선행조건 개수
int result; //선행건물 포함 건설시간
ArrayList<Integer> adjList; //건물이 지어져야 지을수 있는 건물들
public Building() {
this.time= 0;
this.inDegree= 0;
this.result= 0;
this.adjList= new ArrayList<Integer>();
}
}
}https://www.acmicpc.net/problem/1516
1516번: 게임 개발
첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부
www.acmicpc.net
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘]2458번: 키 순서_Java (0) | 2021.10.27 |
|---|---|
| [백준 알고리즘]1922번: 네트워크 연결_Java (0) | 2021.10.26 |
| [백준 알고리즘]1735번: 분수 합_Java (1) | 2021.10.26 |
| [백준 알고리즘] 3955번: 캔디 분배_Java (0) | 2021.10.26 |
| [백준 알고리즘]1256번: 사전_Java (0) | 2021.10.03 |
