백준 1516 게임개발

문제

풀이

public class Q1516_게임개발 {
	
    // 건물을 짓는데 소요되는 시간
    static int[] input;
    // 사전 건물을 짓는데 필요한 시간
    static int[] result;
    // 건물간의 관계를 저장할 배열
    static ArrayList<Integer>[] arr;
    // 진입 차수를 체크할 배열
    static int[] edge;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 건물의 수
        int n = Integer.parseInt(st.nextToken());
        
        input = new int[n + 1];
        result = new int[n + 1];
        
        arr = new ArrayList[n + 1];
        edge = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }
        
        // 건물간의 관계를 초기화
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            input[i] = Integer.parseInt(st.nextToken());
            while (true) {
                int idx = Integer.parseInt(st.nextToken());
                if (idx == -1) {
                    break;
                }
                arr[idx].add(i);
                // 진입 차수 누적
                edge[i]++;
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        // 진입 차수가 0인 노드(건물)만 먼저 큐에 삽입
        for (int i = 1; i <= n; i++) {
            if (edge[i] == 0) {
                q.add(i);
            }
        }
        while (!q.isEmpty()) {
        	// 큐에서 노드 제거
            int now = q.poll();
            for (int next : arr[now]) {
            	// 진입 차수 갱신
                edge[next]--;
                
                // 틀린 로직
//                result[next] = input[now]+result[now];

				// 수정한 로직
                result[next] = Math.max(result[next], result[now] + input[now]);
                if (edge[next] == 0) {
                    q.add(next);
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            System.out.println(input[i]+result[i]);
        }
    }
}

리뷰

이 문제에서 주목해야 할 부분은

1. 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야한다는 것
2. 여러 개의 건물을 동시에 지을 수 있다는 것

이 두가지였다.

나는 단순히 첫번째 사항에만 주목하여 위상정렬로 풀이를 하였는데, 문제에서 주워진 예시는 제대로 결과를 도출하였지만 막상 제출을 하고보니 오답이라는 결과가 나왔다.

여러 건물을 동시에 지을 수 있다는 건 진입 차수에 해당하는 건물을 짓는데 소요되는 시간 중에 최대 시간만 기다리면 되는 것인데, 이 부분을 놓친 것과
진입 차수가 하나가 아닐 수 있다는 당연한 점을 놓치고 있었다.

result[next] = input[now]+result[now];

예를 들어 , c(next)라는 건물을 짓기위해 필요한 건물이 a=6(now), b=3(now)일 경우
여러 건물을 한번에 지을 수 있으므로 두 건물 중 소요시간이 더 큰 a=6이라는 시간을 기다려야 하는데,
처음 작성한 로직대로라면 최대 시간이 아니라 탐색하는 순서에 따라 result[next]가 계속 갱신되어 버린다.

result[next] = Math.max(result[next], result[now] + input[now]);

따라서 현재 저장되어 있는 소요 시간과 현재 값을 비교해 최대 값으로 소요시간을 갱신해줘야 한다.