글 읽기 - 1005 문제 반례 문의

bori12345 3년 전 0

정답을 구하긴했는데, 이해되지 않는 부분이 있어서 질문드립니다.

위상정렬을 통해 구한 트리set 중에 W 포함 트리에 대해서만 비용산정을 하면 된다고 생각했습니다.

실패 케이스가 있는거 같아, 반례가 있는지 도움을 구합니다.

저의 pass / fail 코드를 첨부하겠습니다.

package bj_1005;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static int T, N, K, W; 
	static int D[];
	static int visited[];
	static ArrayList<Integer>[] graph;
	static Queue<Integer> queue;
	static int dist[]; 
	public static void main(String args[]) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		
		for(int test_case =1 ; test_case <=T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());	
			D = new int[N+1];
			
			st = new StringTokenizer(br.readLine());
			for(int i = 1; i <= N; i++) {
				D[i] = Integer.parseInt(st.nextToken());
				
			}
			
			graph = new ArrayList[N+1];

			for(int i = 1; i <= N; i++) {
				graph[i] = new ArrayList();
			}
			
			visited = new int[N+1];
			int indegree[] = new int[N+1];
			for(int i = 1; i <= K; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				graph[a].add(b);
				indegree[b]++;
			}
			
			st = new StringTokenizer(br.readLine());
			W = Integer.parseInt(st.nextToken());
			dist = new int[N+1];
			for(int i = 1;  i <= N; i++) {
				dist[i] = D[i];
			}
			/* pass code 
			for(int i = 1; i <= N; i++) {
				if(indegree[i] == 0) {
					queue = new LinkedList();
					// topology sort
					dfs(i);
					reverse();
					getCost();

				}
			}
			*/
			// fail code 
			for(int i = 1; i <= N; i++) {
				if(indegree[i] == 0) {
					queue = new LinkedList();
					// topology sort
					dfs(i);
					if(queue.contains(W)) {
						reverse();
						getCost();
					}	
				}
			}
			System.out.println(dist[W]);
			
		}
	}
	
	public static void getCost() {
		
		while(!queue.isEmpty()) {
			int num = queue.poll();
			
			for(int adj : graph[num]) {
				if(dist[adj] < dist[num]+D[adj]) {
					dist[adj] = dist[num]+D[adj];
				}	
			}	
		}
	}
	

	public static void dfs(int num) {
		// 1. 목적지에 도착했는가
		// 2. 체크인
		visited[num] = 1; 
		// 3. 연결된 곳을 순회
		for(int adj : graph[num]) {
			//4. 갈수 있는곳인가
			if(visited[adj] == 0) {
				// 5. 방문
				dfs(adj);
			}
		}
		// topology sort
		queue.offer(num);		
	}
	
	public static void reverse() {
		Stack<Integer> tmp = new Stack<>();
		
		while(!queue.isEmpty()) {
			tmp.add(queue.peek());
			queue.remove();
		}
		
		while(!tmp.isEmpty()) {
			queue.add(tmp.peek());
			tmp.pop();
		}
	}

}


class Vertex {
	int num; 
	int weight;
	public Vertex(int num, int weight) {
		super();
		this.num = num;
		this.weight = weight;
	}

}

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

문제

문제

출처

ICPC

1005 문제 반례 문의

bori12345 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말