문제의 힌트 : 모든 도로가 일방향이고, 사이클이 없다. → 여기서 전에 풀었던 문제들과 비슷하다는 걸 느껴야.

문제 이해

코드 (1차)

Q) time도 value 로 각 도로에 연결된 값인데, 이 time은 어떻게 저장해야 할까?

/*
 * 2025-07-11
 * 문제55_백준 1948번
 * */

package day8.B1948;

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

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());
        int M = Integer.parseInt(br.readLine());

        List<List<Integer>> list = new ArrayList<>();

        for(int i = 0; i <= N; i++){
            list.add(new ArrayList<>());
        }

        for(int i = 0; i < M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            list.get(node1).add(node2);
        } // 여기서 time을 어디다 어떻게 저장할건지?

        

        br.close();
    }
}

A) 간선 객체를 하나 만들어서 정점과 시간을 같이 묶는다!

1. 간선 클래스 정의

class Edge{
	int to;
	int time;
	
	Edge(int to, int time){
		this.to = to;
		this.time = time;
	}
}

1. 리스트 선언을 바꾸기

List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
    graph.add(new ArrayList<>());
}

1. 간선 정보 저장 시에는

int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());

int time = Integer.parseInt(st.nextToken());

graph.get(from).add(new Edge(to, time));

Q2) 1. 각 노드까지 도달하는데 걸리는 최장 시간은 어디에 저장?

→ 노드까지 도달하는 최장 시간 저장용 배열을 따로 만들어야 한다.

→ 앞 문제에서 rslt[ ] 와 같은 것