글 읽기 - 반례돌려도 정답인데 채점 53%에서 틀렸다고 나오네요.

issuemine 5년 전 0

BFS를 1번 돌리고, 가장 먼 node를 찾은 뒤 가장 먼 node에서 BFS를 다시 하여

가장 먼 node를 찾는 식으로 문제를 풀었습니다. 53%까지는 정답으로 올라가다가

틀렸다고 나오는데... 어디가 틀렸는지 도대체 모르겠네요..

한수 알려주시면 감사하겠습니다. ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {
	private int node;
	
	private int dist;

	public Node(int node, int dist) {
		this.node = node;
		this.dist = dist;
	}

	public int getNode() {
		return node;
	}

	public void setNode(int node) {
		this.node = node;
	}

	public int getDist() {
		return dist;
	}

	public void setDist(int dist) {
		this.dist = dist;
	}
}

public class Main {
	public static ArrayList<ArrayList<Node>> tree = new ArrayList<>();
	public static int[] dist;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.valueOf(br.readLine());
		
		dist = new int[n + 1];
		
		for (int i = 0; i < n + 1; i++) {
			tree.add(new ArrayList<Node>());
		}
		
		int numOfNumber = n;
		
		while (numOfNumber > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int count = st.countTokens();
			
			int pivotNode = Integer.valueOf(st.nextToken());
			int addNode = 0;
			int distance = 0;
			for (int i = 0; i < count - 1; i++) {
				
				if (i % 2 == 0) {
					addNode = Integer.valueOf(st.nextToken());
					if (addNode == -1) {
						break;
					}
				} else {
					distance = Integer.valueOf(st.nextToken());
					tree.get(pivotNode).add(new Node(addNode, distance));
				}
				
			}
			numOfNumber--;
		}
		
		dist[1] = -1;
		bfs(tree.get(1).get(0));
		
		int maxNode = 1;
		for (int i = 1; i <= n; i++) {
			if (dist[maxNode] < dist[i]) {
				maxNode = i;
			}
		}
		
		for (int i = 1; i <= n; i++) {
			dist[i] = 0;
		}
		
		dist[maxNode] = -1;
		bfs(tree.get(maxNode).get(0));
		
		int result = dist[1];
		for (int i = 1; i <= n; i++) {
			if (result < dist[i]) {
				result = dist[i];
			}
		}
		
		bw.write(result + "\n");
		bw.flush();
		bw.close();
	}
	
	public static void bfs(Node start) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(start);
		
		dist[start.getNode()] = start.getDist();
		
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			for (Node child : tree.get(node.getNode())) {
				if (dist[child.getNode()] == 0) {
					dist[child.getNode()] = dist[node.getNode()] + child.getDist();
					queue.add(child);
				}
			}
		}
	}
}

issuemine 5년 전 0

감사합니다. 1번 정점에서 시작하는 것이 아니였네요.

해결되었습니다.!

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

문제

문제

출처

ICPC

반례돌려도 정답인데 채점 53%에서 틀렸다고 나오네요.

issuemine 5년 전 0

issuemine 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말