글 읽기 - bfs로 풀었는데 반례를 모르겠습니다.

sj155 4년 전 0

사용한 방법은 1번 정점에서 가장 멀리 떨어져 있는 점 구하기 -> 그 점에서 가장 길이가 먼 곳 구하는 방식입니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool chk[100001];
int dis[100001];

int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);

	queue <int> que;
	int n, x, y = 1, bigNode = 1, leng = 0;

	cin >> n;

	vector <vector<int>> arr(n + 1);

	for (int i = 1; i <= n; i++)
	{
		cin >> x;

		while (1)
		{
			cin >> y;

			if (y == -1)//-1 입력받으면 다음 줄 입력 받습니다.
			{
				y = 1;
				break;
			}
			arr[x].push_back(y);
		}
	}

	que.push(1);//시작 정점입니다

	while (que.size())
	{
		int node = que.front();

		for (int j = 0; j < arr[node].size(); j += 2)//2씩 커져서 정점만 보여줍니다.
		{
			if (chk[arr[node][j]] == false)//방문한 적이 있으면 넘어갑니다
			{
				que.push(arr[node][j]);

				dis[arr[node][j]] = dis[node] + arr[node][j + 1];//거리 추가하는 부분입니다

				if (dis[arr[node][j]] > leng)
				{
					bigNode = arr[node][j];
				}
			}
		}
		chk[node] = true;
		que.pop();
	}

//	cout << bigNode << endl; 

	que.push(bigNode);

	bigNode = 0;
	leng = 0;

	for (int i = 1; i <= n; i++)//0으로 만들어주는 부분입니다
	{
		chk[i] = false;
		dis[i] = 0;
	}

	while (que.size())
	{
		int node = que.front();

		for (int j = 0; j < arr[node].size(); j += 2)
		{
			if (chk[arr[node][j]] == false)
			{
				que.push(arr[node][j]);

				dis[arr[node][j]] = dis[node] + arr[node][j + 1];

				if (dis[arr[node][j]] > leng)
				{
					leng = dis[arr[node][j]];
				}
			}
		}
		chk[node] = true;
		que.pop();
	}

	cout << leng;

	return 0;
}

djm03178 4년 전 0

53번째 줄에서 leng보다 더 먼 정점을 찾았으면 leng도 갱신이 되어야 하는데, 하고 있지 않아서 leng이 계속 0으로 남아있기 때문에 bigNode가 무조건 갱신되어 버립니다.

sj155 4년 전 0

으악.. 너무 기초적인 부분을 놓치고 지나갔습니다. 감사합니다.

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

문제

문제

출처

ICPC

bfs로 풀었는데 반례를 모르겠습니다.

sj155 4년 전 0

djm03178 4년 전 0

sj155 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말