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

 

 

1167번: 트리의 지름

 

문제!

---

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

---

간단하네요...

 

 

입력은 차례대로

5 // 정점의 갯수
1 3 2 -1 // 정점의 번호 // 연결된 정점 // 그 정점과의 거리
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

// -1이면 끝!

 

순서대로 받아옵니다.

 

이제 정점간의 가장 긴 거리 = 트리의 지름 을 구해야합니다.

 

저는 일단 각 정점에서 갈 수 있는 노드에 대해 정리해둔다음

1. 임의의 정점에서 가장 끝에 있는 정점 찾기

2. 그 정점에서 가장 멀리있는 정점 찾기

 

이런 방식으로 문제를 해결하였습니다.

 

 

 

바로 코드!

---

먼저 입력값을 받아옵시다.

 

int N;  // 정점수

vector<int> connectList[100001]; // 이어진 정점
vector<int> distanceList[100001]; // 정점과의 거리

 

 

두 벡터에 정점과 거리를 따로 저장해 주었습니다. 

cin >> N;

	for (int i = 0; i < N;i++) {
		int tempNum;
		cin >> tempNum;

		int temp=1;
		int distance;

		while (true) {
			cin >> temp;
			if (temp == -1) {
				break;
			}
			cin >> distance;

			connectList[tempNum].push_back(temp);
			distanceList[tempNum].push_back(distance);
		}
	}

 

 

이제 위의 두 벡터를 이용하여 dfs탐색을 돌려줍시다.

bool visit[100001]; // 방문
int maxDist, SaveNode;

...

void dfs(int node, int dist)
{
	if (visit[node])
		return;

	if (maxDist < dist) // 제일 멀리떨어진 노드 찾기
	{
		maxDist = dist;
		SaveNode = node;
	}

	visit[node] = true;

	for (vector<int>::size_type i = 0; i < connectList[node].size(); i++)
	{
		int nextIndex = connectList[node][i];
		int nextDist = distanceList[node][i];
		dfs(nextIndex, nextDist + dist);
	}
}

 

 

다음은 차례대로 

임의의 정점에서 가장 먼 지점을 SaveNode에 저장해두고

그 점에서 다시 가장 먼 지점을 찾아 거리를 출력해줍시다.

dfs(1, 0);

	memset(visit, 0, sizeof(visit)); // 초기화 해주고 다시
	maxDist = 0;

	dfs(SaveNode, 0);

 

 

 

이러면끝!

 

끝에서 끝으로 탐색을 한다는 점만 생각해내면 쉽게 해결할 수 있는 문제였습니다!

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;


int N;  // 정점수

vector<int> connectList[100001]; // 이어진 정점
vector<int> distanceList[100001]; // 정점과의 거리



bool visit[100001]; // 방문
int maxDist, SaveNode;


void dfs(int node, int dist)
{
	if (visit[node])
		return;

	if (maxDist < dist) // 제일 멀리떨어진 노드 찾기
	{
		maxDist = dist;
		SaveNode = node;
	}

	visit[node] = true;

	for (vector<int>::size_type i = 0; i < connectList[node].size(); i++)
	{
		int nextIndex = connectList[node][i];
		int nextDist = distanceList[node][i];
		dfs(nextIndex, nextDist + dist);
	}
}



int main() {
	cin >> N;

	for (int i = 0; i < N;i++) {
		int tempNum;
		cin >> tempNum;

		int temp=1;
		int distance;

		while (true) {
			cin >> temp;
			if (temp == -1) {
				break;
			}
			cin >> distance;

			connectList[tempNum].push_back(temp);
			distanceList[tempNum].push_back(distance);
		}
	}


	dfs(1, 0);

	memset(visit, 0, sizeof(visit)); // 초기화 해주고 다시
	maxDist = 0;

	dfs(SaveNode, 0);



	cout << maxDist << endl;

	return 0;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!