글 읽기 - 경로를 찍는 좋은 방법좀 알려주세요...

windy10928 3년 전 0

안녕하세요. 해당 문제 테스트 케이스 구해서 해보니 최대 이익과 탐색한 동굴의 수는 잘 나오는거 같은데

경로를 찍는 부분에서 틀리는거 같습니다. 뭐가 문제인지 모르겠네요 ㅠ visited 배열로 메모이제이션 한 걸로 각 노드에 최대 이익이 나와 있고

find() 함수에 보시면 visited[idx] - map[idx] == visited[i] - cost 에 조건에 해당하는 노드를 이전 노드로 생각하고 재귀적으로 호출해서 1까지 다시 올라갔습

니다.

무엇이 틀린걸까요 ㅠㅠ... 경로 찍는거 너무 어렵네요...

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

class Main {
	
	static int T;
	static int N,E;
	static int[] map;
	static ArrayList<Node> [] adj;
	static int[] visited;
	static int max;
	static int maxIdx;
	static int maxCnt;
	static boolean find;
	static ArrayList<Integer> list = new ArrayList<>();
	
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			
			map = new int[N+1];
			visited = new int[N+1];
			adj = new ArrayList[N+1];
			
			for (int i = 0; i <= N; i++) {
				adj[i] = new ArrayList<Node>();
			}
			
			st = new StringTokenizer(br.readLine());
			
			for (int i = 1; i <= N; i++) {
				map[i] = Integer.parseInt(st.nextToken());
			}
			
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				adj[a].add(new Node(b, c));
			}
			
			Arrays.fill(visited, Integer.MIN_VALUE);
			
			max = map[1];
			maxIdx = 1;
			maxCnt = 1;
			
			visited[1] = map[1];
			solve(1,1);
			
			list.add(maxIdx);
			find = false;
			find(maxIdx);
			
			StringBuffer sb = new StringBuffer();
			
			for (int i = list.size()-1; i >= 0; i--) {
				sb.append(list.get(i));
				if(i != 0) sb.append(" ");
			}
			
			System.out.println(max+" "+maxCnt);
			System.out.println(sb.toString());
			list.clear();
		}
	}
	
	static void find(int idx) {
		
		if(find) return ;
		
		if(idx == 1) {
			find = true;
			return ;
		}
		
		for (int i = 1; i <= N; i++) {
			int cost = getCost(i, idx);
			if(cost == -1) continue;
			if(visited[idx] - map[idx] == visited[i] - cost) {
				list.add(i);
				find(i);
			}
			if(find) return ;
		}
	}
	
	static int getCost(int from, int to) {
		for (int j = 0; j < adj[from].size(); j++) {
			Node node = adj[from].get(j);
			if(node.idx == to) {
				return node.cost;
			}
		}
		return -1;
	}
	
	static void solve(int cnt, int cur) {
		if(max < visited[cur]) {
			max = visited[cur];
			maxCnt = cnt;
			maxIdx = cur;
		}
		
		for (int i = 0; i < adj[cur].size(); i++) {
			Node node  = adj[cur].get(i);
			int next = node.idx;
			int nCost = node.cost;
			
			if( visited[next] >= visited[cur] + map[next] - nCost) continue;
			
			visited[next] = visited[cur] + map[next] - nCost;
			solve(cnt+1, next);
		}
	}
	
}

class Node	 {
	int idx;
	int cost;
	
	Node (int idx, int cost) {
		this.idx = idx;
		this.cost = cost;
	}
}

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

문제

문제

출처

ICPC

경로를 찍는 좋은 방법좀 알려주세요...

windy10928 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말