글 읽기 - 트리의 지름.. BFS 로 풀었을 때..

sgchoi5 6년 전 0

다른 트리의 지름 문제는 DFS 로 풀어봤던터라, 이번 트리의 지름 문제는 BFS 로 풀어 봤는데,

어디가 문제인지 모르겠네요.. 4% 보고 틀리네요..

BFS 로도 되야 할 것 같은데, 어디가 문제가 있는 것인지.... 조언 좀 부탁드려요~~

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

vector<pair<int, int>> tree[100001];
bool visited[100001];

pair<int, int> BFS(int start, int size) {
	int distance = 0;
	int numV = 0;

	for (int i = 1; i <= size; i++) {
		visited[i] = false;
	}

	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	while (q.empty() == false) {
		pair<int, int> curV = q.front();
		q.pop();

		int num = tree[curV.first].size();
		for (int i = 0; i < num; i++) {
			if (visited[tree[curV.first][i].first] == false) {
				visited[tree[curV.first][i].first] = true;
				if (distance < curV.second + tree[curV.first][i].second) {
					distance = curV.second + tree[curV.first][i].second;
					numV = tree[curV.first][i].first;
				}
				q.push({ tree[curV.first][i].first, curV.second + tree[curV.first][i].second });
			}
		}
	}
	return { numV, distance };
}

int main(void) {
	int V, temp, distance, ans = 0;
	scanf("%d", &V);
	for (int i = 1; i <= V; i++) {
		scanf("%d", &temp);

		while (scanf("%d", &temp), temp != -1) {
			scanf("%d", &distance);
			tree[i].push_back({ temp, distance });
		}
	}

	pair<int, int> start, end;
	start = BFS(1, V);
	end = BFS(start.first, V);

	printf("%d\n", end.second);
	return 0;
}

atomzeno 6년 전 0

또 이런 질문이 ㄷㄷ

~~입력에서 i+1 번쨰 줄의 정점이 i라는 말이 없다니깐~~

jung2381187 6년 전 1

5
5 4 6 -1
4 2 4 3 3 5 6 -1
3 1 2 4 3 -1
2 4 4 -1
1 3 2 -1

kks227 6년 전 33

@atomzeno 평소에도 모르는 분에게 그렇게 말하세요?

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

문제

문제

출처

ICPC

트리의 지름.. BFS 로 풀었을 때..

sgchoi5 6년 전 0

atomzeno 6년 전 0

jung2381187 6년 전 1

kks227 6년 전 33

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말