BOJ - 게임 개발 1516번 (JAVA)

❓ 문제 - 백준 게임 개발 1516번 - JAVA 풀이법

 

출처

(https://www.acmicpc.net/problem/1516)

1516번: 게임 개발

 

 

 

📝 문제해결법

1. 문제

• 건물의 종류 수가 N(1 <= N <= 500)일 때 하나의 건물을 짓기 위해 지어지는 시간과 그 전에 먼저 지어져야 하는 건물의 정보를 주어질 때 각 모든 건물을 짓기 위해 걸리는 시간을 하나씩 출력하라.

 

2. 해결 방법

• 건물의 수가 (1 <= n < 500)이고 한 건물을 짓기 전에 다른 건물들이 먼저 지어져야 할 때, 다른 건물들이 지어지는 시간을 참조하면 되므로 구할 때 dfs와 dp를 활용한다.
• time 배열에 각 건물이 지어질 때 필요한 시간을 입력받고, connect로 i번째 건물이 지어지기 위해 먼저 지어져야 하는 건물의 번호를 list에 add한다.
• 그리고 1번 건물부터 dfs를 호출해서 1번 건물을 짓기 위해 먼저 지어져야 하는 건물들의 정보를 가져오고 이미 dp 배열-> ans에 값이 지정되었으면 그 값을 활용하고 만약 아직 구해지지 않았으면 다시 dfs를 통해 구하도록 한다.
• 이 문제는 n의 범위가 500보다 작고, dp를 활용하면 시간 2초 내에 구할 수 있는 문제이다.

 

3. 느낀점

• 그래프 이론과 dp 두 가지 방법만을 이용하면 쉽게 접근할 수 있는 문제 같다.
• 다른 사람들의 풀이를 보니 위상정렬로 queue를 활용하는데 나의 풀이법과 메모리 사용과 시간이 비슷한 것 같다.

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_1516 {
    public static int n;
    public static int[] time;
    public static int[] ans;
    public static ArrayList<Integer>[] connect;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        n = Integer.parseInt(br.readLine());
        time = new int[n+1];
        ans = new int[n+1];
        connect = new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            connect[i] = new ArrayList<Integer>();
        }

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            time[i] = Integer.parseInt(st.nextToken());
            while (true){
                int num = Integer.parseInt(st.nextToken());
                if(num == -1) break;
                connect[i].add(num);
            }
        }

        for(int i=1;i<=n;i++){
            dfs(i);
            System.out.println(ans[i]);
        }
    }

    public static int dfs(int number){
        if(ans[number] != 0) return ans[number];
        ans[number] += time[number];
        int max = 0;
        for(int c:connect[number]){
            max = Math.max(max, dfs(c));
        }
        ans[number] += max;
        return ans[number];
    }
}