백준 | 18126번. 너구리 구구 - DFS, BFS 풀이

⬛ 백준 18126번. 너구리 구구 - DFS, BFS 풀이

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

18126번: 너구리 구구

[주의] long 타입으로 변수를 선언해야 정답이 맞다.

길 하나의 길이가 10억이고, 방은 최대 5,000개까지 존재하므로 특정 방까지의 이동 거리는 최대 5^12까지이므로 long 타입을 사용해야 한다.

문제

텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.  구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.

다음 N-1개의 줄에 구구의 집의 모든 길의 정보가 정수 A, B, C(1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)로 주어진다.

A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C임을 의미한다.

출력

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

💚나의 풀이

package to_0829_3;

import java.util.ArrayList;
import java.util.Scanner;

/*18126번. 너구리 구구 문풀 -long 타입으로 답 풀어야 한다. */
class Node {
	int v;
	long val;
	Node(int v, long val){
		this.v = v;
		this.val =val;
	}
}
public class Main {
	static int N;
	static boolean[] visited;
	static ArrayList<ArrayList<Node>> graph;
	static long[] length; //여기에 각 1부터 정점까지의 거리 담기 S
	//DFS
	static void DFS(int v, long len) {
		visited[v] = true;
		
		for(Node nx : graph.get(v)) {
			int nx_v = nx.v;
			long nx_val = nx.val;
			//v의 인접 정점에 대하여 
			if(!visited[nx_v]) {
				length[nx_v] = len + nx_val;
				DFS(nx_v, length[nx_v]);
			}
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		N = kb.nextInt();
		visited = new boolean[N+1];
		length = new long[N+1];
		graph = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		
		//데이터 입력받기 
		for(int i=0; i<N-1; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int val = kb.nextInt();
			
			//양방향이므로 
			graph.get(a).add(new Node(b, val));
			graph.get(b).add(new Node(a, val));
		}
		
		DFS(1, 0);
		
		long max=0;
		for(int i=1; i<=N; i++) {
			max = Math.max(max, length[i]);
		}
		System.out.println(max);
	}
}