글 읽기 - 많이 고민해봤지만 어디가 틀린건지 전혀 모르겠습니다ㅠㅠ

cheolyeing_j 3년 전 0

child가 없는 node부터 Queue에 삽입하여

부모 노드로 올라가며 최대 경로를 갱신해주고,

child끼리 만나게 되는 부모 node 라면 child중 최대 경로 2개를 더해 ans에 갱신해줬습니다.

n = 1 인 경우,

n = 2 인 경우,

일직선으로 된 트리인 경우

child의 수가 3개 이상인 경우

이정도의 반례를 생각해보고 테스트케이스를 만들어봤지만 실패했습니다...

어디가 잘못된걸까요?? 고수님들 도와주세요ㅠㅠ

import java.io.*;
import java.util.*;
import java.awt.*;

public class Main {
	/*
	 * n : 노드의 갯수
	 * ans : 정답
	 * dist[i] : i번째 노드까지 오는 최대 경로
	 * parent[i] : i번째 노드의 parent, weight 순
	 * visited : 방문 check
	 */
	static int n, ans=0, dist[];
	static Point[] parent;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		setting();
		solution();
	}
	
	static void setting () throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		dist = new int[n+1];
		visited = new boolean[n+1];
		parent = new Point[n+1];
		Arrays.fill(dist, -1);
		parent[1] = new Point(0, 0);
		
		for(int i=1; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			parent[c] = new Point(p, w);
			dist[p] = 0;
		}
	}
	
	static void solution() {
		/// child가 없는 노드부터 큐에 삽입
		Queue<Integer> q = new LinkedList<Integer>();
		for(int i=1; i<=n; i++) {
			if(dist[i]!=0) {
				visited[i] = true;
				q.add(i);
				dist[i] = 0;
			}
		}
		
		Loop :
		while(!q.isEmpty()) {
			int size = q.size();
			
			for(int i=0; i<size; i++) {
				int c = q.poll();
				if(c==0) break Loop;
				int p = parent[c].x;
				// 큐에서 나온 child로 parent를 구하고 parent까지의 최대 경로를 갱신
				int newDist = dist[c] + parent[c].y;
				
				ans = Math.max(ans, dist[p]+newDist);
				dist[p] = Math.max(dist[p], newDist);	
				
				if(!visited[p]) q.add(p);
				visited[p] = true;
			}
		}
		
		System.out.println(ans);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

많이 고민해봤지만 어디가 틀린건지 전혀 모르겠습니다ㅠㅠ

cheolyeing_j 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말