99클럽 코테 스터디 17일차 TIL (챌린저): [백준][Java] 2056 작업 - 골드4

 

문제 보기

https://www.acmicpc.net/problem/2056

 

 

풀이

최소 시간을 구하는 문제이지만

그래프 탐색을 한다고 생각해보면 선행해야 하는 작업 중 가장 느린 작업이 끝나는 시간을 반영해야 하기 때문에

BFS를 진행하며 최대 시간을 구하는 방법을 생각했었다...

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import org.w3c.dom.Node;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    List<Integer>[] list = new LinkedList[N + 1];
    for(int i = 1; i <= N; i++) {
      list[i] = new LinkedList<>();
    }

    Queue<Node> queue = new LinkedList<>();
    int[] dist = new int[N+1];
    for(int i = 1; i <= N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      list[i].add(Integer.parseInt(st.nextToken()));
      int length = Integer.parseInt(st.nextToken());
      if(length == 0) {
        queue.add(new Node(i, list[i].get(0)));
        dist[i] = list[i].get(0);
      }
      for(int j = 0; j < length; j++) {
        list[Integer.parseInt(st.nextToken())].add(i);
      }
    }

    int max = 0;
    while(!queue.isEmpty()) {
      Node node = queue.poll();

      max = node.dist;
      for(int i = 1; i < list[node.node].size(); i++) {
        int next = list[node.node].get(i);
        if(dist[next] >= node.dist + list[next].get(0)) continue;
        dist[next] = node.dist + list[next].get(0);
        queue.add(new Node(next, dist[next]));
      }
    }

    bw.write(max + "\n");

    bw.flush();
    bw.close();
  }

  static class Node {
    int node, dist;
    public Node(int node, int dist) {
      this.node = node;
      this.dist = dist;
    }
  }
}

예상했듯 결과는 시간초과였다.

그래서 알고리즘 분류를 보니 dp가 있었고 어떻게 풀어야 할지 감이 왔다.

 

for(int i = 1; i <= N; i++) {
  StringTokenizer st = new StringTokenizer(br.readLine());
  int time = Integer.parseInt(st.nextToken());
  int length = Integer.parseInt(st.nextToken());
  if(length == 0) {
    dp[i] = time;
  }
  for(int j = 0; j < length; j++) {
    dp[i] = Math.max(dp[i], dp[Integer.parseInt(st.nextToken())] + time);
  }
  max = Math.max(max, dp[i]);
}

이 부분이 핵심 코드이다.

선행 노드 + 현재 작업 시간을 더한 값과

이전에 기록된 현재 작업까지 시간을 비교하며

최대시간을 기록한다.

 

위 BFS 풀이와 논리는 동일하다.

 

물론 N번 노드가 항상 마지막 노드일 거란 보장은 없기 때문에 max값을 따로 기록 해주고 있다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    int[] dp = new int[N+1];
    int max = 0;
    for(int i = 1; i <= N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int time = Integer.parseInt(st.nextToken());
      int length = Integer.parseInt(st.nextToken());
      if(length == 0) {
        dp[i] = time;
      }
      for(int j = 0; j < length; j++) {
        dp[i] = Math.max(dp[i], dp[Integer.parseInt(st.nextToken())] + time);
      }
      max = Math.max(max, dp[i]);
    }

    bw.write(max + "\n");

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2056.%E2%80%85%EC%9E%91%EC%97%85

CodingTest_AutoSave/백준/Gold/2056. 작업 at main · MetroDefro/CodingTest_AutoSave