3. 그래프 최대점수 (+DFS)

 

+) 세련된 풀이

: DFS

각 노드를 무한 반복해, ch 배열로 첫 번째로 방문 했는지를 확인

 

import java.util.*;
class Edge {
    public int vex;
	public int cost;
    Edge(int vex, int cost) {
        this.vex = vex;
        this.cost = cost;
    }
}
class Main {
	public int answer=0;
	public ArrayList<ArrayList<Edge>> graph;
	public int[] ch;
	public void DFS(int cur, int time, int sum, int[] nums){
		if(time<0) return;
		ch[cur]++;
		if(ch[cur]==1) sum+=nums[cur];
		if(cur==0) answer=Math.max(answer, sum);
		for(Edge x : graph.get(cur)){
			DFS(x.vex, time-x.cost, sum, nums);
		}
		ch[cur]--;
	}
	public int solution(int[] nums, int[][] edges, int k){
		int n=nums.length;
		graph = new ArrayList<ArrayList<Edge>>();
		for(int i=0; i<=n; i++){
			graph.add(new ArrayList<Edge>());
		}
		for(int[] x : edges){
			graph.get(x[0]).add(new Edge(x[1], x[2]));
			graph.get(x[1]).add(new Edge(x[0], x[2]));
		}
		ch=new int[n];
		DFS(0, k, 0, nums);
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		int[] arr={5, 25, 10, 30};
		int[][] edges={{0, 1, 11}, {1, 2, 15}, {0, 3, 12}};
		System.out.println(T.solution(arr, edges, 47)); //60	
	}
}