개발자 톡

연습문제 톡 [21년 재직자 대회 본선] 거리 합 구하기

[재직자 본선 거리합 문제], Algo Tutor에 있는 로직 그대로 java에 옮겼는데 왜 틀릴까요..?

등록일
2022-01-04 12:47:25
조회수
1166
작성자
zaza1994

몇가지 테스트 케이스 직접 돌려보고 같은 값이 나오는 거 확인했습니다.

도대체 어느 부분에서 문제가 되는지 알고 싶습니다.

도와주세요

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class Main {
 	static int N;
 	static LinkedList[] nodes;
	static int[] ans, subTree, distSum;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		nodes = new LinkedList[N+1];
		ans = new int[N+1];
		subTree = new int[N+1];
		distSum = new int[N+1];
		for(int n = 0; n < N+1; n++) nodes[n] = new LinkedList<>();
		
		for(int n = 0; n < N-1; n++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			nodes[n1].add(new Integer[]{n2,c});
			nodes[n2].add(new Integer[]{n1,c});
		}
		dfs1(1,0);
//		for(int n = 0; n < N; n++) System.out.println(distSum[n+1]);
		dfs2(1,0);
		for(int n = 0; n < N; n++) System.out.println(distSum[n+1]);
	}

	
	static void dfs1(int cur, int prv) {
		subTree[cur] = 1;
		for(Integer[] arr : nodes[cur]) {
			int child = arr[0];
			int weight = arr[1];
			if(child != prv) {
				dfs1(child, cur);
				distSum[cur] += distSum[child] + subTree[child]*weight;
				subTree[cur] += subTree[child];
				
			}
		}
	}
	
	static void dfs2(int cur, int prv){
		for(Integer[] arr : nodes[cur]) {
			int child = arr[0];
			int weight = arr[1];
			if(child != prv) {
				distSum[child] = distSum[cur] + weight*(N-2*subTree[child]);
				dfs2(child, cur);
			}
		}
		
	}

	
}



#[21년_재직자_대회_본선]_거리_합_구하기
#거리합문제
#java

이 카테고리의 톡 더보기