[C++] 백준 1167번 트리의 지름

[C++] 백준 1967번 트리의 지름

위 문제와 거의 똑같은 문제.

차이점이라면,

1. 루트 노드가 1이 아니다.
2. 정점 번호가 작은 순서부터 입력되는 것이 아니라 랜덤으로 입력된다.
3. -1이 나오기 전까지 노드를 연결시킨다.

정도가 되겠다. 3번 차이점은 사실 크게 중요하지는 않다.

위에 링크를 남긴 문제를 풀었다면 이 문제도 아마 크게 어렵지 않게 풀 수 있다.

 

문제풀이

자세한 풀이는 생략하겠다. (위 비슷한 문제와 거의 똑같은 방식으로 풀었다.)

우선, 루트 노드가 무엇인지 주어지지 않는다.

 

근데 내가 푼 풀이의 경우에는 아무런 노드 하나를 루트 노드로 설정해서

DFS를 시작하면 모든 노드에서 가능한 트리의 지름을 모두 구할 수가 있다.

 

어떤 번호부터 DFS를 시작해야할 지 모르므로, 1번부터 시작해서 100000번까지 중

최초로 만나는 그래프의 노드 번호를 DFS 시작 노드(루트 노드)로 설정해서 풀었다.

 

/*
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int vertexCnt;
vector<pair<int, int>> adjVec[100001];
vector<int> distVec[100001];
bool visit[100001];
int ans;

int dfs(int vertexNum) {
	visit[vertexNum] = true;

	for (pair<int, int> p : adjVec[vertexNum]) {
		int nextVertexNum = p.first;
		int distance = p.second;

		if (!visit[nextVertexNum]) {
			int checkDist = distance + dfs(nextVertexNum);
			distVec[vertexNum].push_back(checkDist);
		}
	}

	sort(distVec[vertexNum].begin(), distVec[vertexNum].end());

	if (distVec[vertexNum].size() == 0) {
		return 0;
	}
	else if (distVec[vertexNum].size() == 1) {
		ans = max(ans, distVec[vertexNum][0]);
		return distVec[vertexNum][0];
	}
	else {
		int firstBigIdx = distVec[vertexNum].size() - 1;
		int secondBigIdx = distVec[vertexNum].size() - 2;

		int checkDiameter = distVec[vertexNum][firstBigIdx] + distVec[vertexNum][secondBigIdx];
		ans = max(ans, checkDiameter);

		return distVec[vertexNum][firstBigIdx];
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> vertexCnt;

	int vertexNum, adjVertexNum, distance;
	for (int i = 1; i <= vertexCnt; i++) {
		cin >> vertexNum;
		while (true) {
			cin >> adjVertexNum;
			if (adjVertexNum == -1) { break; }
			cin >> distance;
			adjVec[vertexNum].push_back({ adjVertexNum, distance });
		}
	}

	for (int i = 1; i <= 100000; i++) {
		if (!visit[i] && adjVec[i].size() > 0) {
			dfs(i);
			break;
		}
	}

	cout << ans;

	return 0;
}

코드 전문.

 

위에 유사한 문제 1967번과 거의 똑같다.

 

처음에 for반복문 범위를 잘못설정했어서 틀렸다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.