[BOJ] 1167 트리의 지름

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

문제

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

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

입력	출력
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	11

주어진 트리

---

문제를 읽다보니 트리도 결국 그래프이므로 어제 푼 문제랑 비슷하더라.

그런데 어제 푼 문제의 조건이 생각이 안 나서 앞으로는 조건도 같이 써놔야겠다는 생각이 들었다.

어제는 1번 노드로부터 가장 먼 거리를 찾았는데 이번엔 따로 시작점이 정해져 있지 않았다.

https://uyt8989.tistory.com/9

[프로그래머스] 가장 먼 노드

 

그래서 떠올린 방법은 Floyd 알고리즘이다. 

모든 점에서 다른 모든 점에 대해 최단거리를 구하고 그중에 가장 큰 값을 답으로 결정하면 되지 않을까 했는데 

단순히 인접 행렬을 사용하기에는 정점의 개수가 10만 개라 불가능했다.

생각해보니 시간 제약도 맞추지 못할 것 같았다.

그래서 인접리스트를 생각했는데 백준 문제에서 써본 적이 없어서 다른 쌈박한 방법이 있지 않을까 했다.

하지만 결국 못 찾았고 인접 리스트를 구현했다.

 

인접 리스트

 

근데 구현해놓고 보니 내가 C가 아니라 C++을 쓰고 있었다...

벡터 썼으면 더 쉽게 갔을 것 같은데... 숙련도 이슈...ㅎ

그리고 인접 리스트로 Floyd를 적용하기 어려워보였다.

그래서 그냥 DFS를 쓰기로 하고 제출했는데 시간 초과가 떴다.

주어진 그래프가 트리니까 사이클이 없다는 조건을 활용하면 풀 수 있을 것 같았지만

결국 못 알아내고 블로그를 참고했다.

 

다른 블로그를 참고해보니 거의 근접했는데 좀만 더 생각해볼걸 싶었다.

임의의 한 점에서 DFS를 한번 적용해서 가장 먼 노드를 찾는다.

그 노드에서 다시 DFS를 적용해서 가장 먼 노드를 찾으면 그때의 비용이 정답이 된다.

 

#include <iostream>
#include <cstring>

typedef struct _Node {
	int v;
	int cost;
	_Node* next;
}node;

int V;
node vertex[100001];
bool visit[100001];
int max, max_node;

void DFS(int start, int cost) {
	node* temp = vertex[start].next;
	visit[start] = true;

	while (temp != NULL) {
		if (visit[temp->v] == false) {
			if (cost + temp->cost > max) {
				max = cost + temp->cost;
				max_node = temp->v;
			}
			DFS(temp->v, cost + temp->cost);
		}
		temp = temp->next;
	}
}

int main() {
	int ver, v, cost;
	node* temp;

	std::cin >> V;

	for (int i = 1; i <= V; i++) {
		std::cin >> v;
		vertex[v].next = NULL;
		
		vertex[v].v = v;

		while (1) {
			std::cin >> ver;
			if (ver == -1) break;
			
			std::cin >> cost;

			temp = (node *)malloc(sizeof(node));
			temp->v = ver; temp->cost = cost;
			temp->next = vertex[v].next;
			vertex[v].next = temp;
		}
	}


	memset(visit, false, sizeof(visit));
	DFS(1, 0);
	memset(visit, false, sizeof(visit));
	max = 0;
	DFS(max_node, 0);

	std::cout << max;
	
	for (int i = 1; i <= V; i++) {
		while (vertex[i].next != NULL) {
			temp = vertex[i].next;
			vertex[i].next = (vertex[i].next)->next;
			free(temp);
		}
	}

	return 0;
}

 

후기)

파일을 cpp로 만들고 열심히 C로 풀었다...ㅋ

인접 리스트 자체는 구현하는게 맞았는데 괜히 어렵게 했다.

입력을 받을 때 당연히 순서대로 들어오는 줄 알았는데 알고보니 아니었다. 릭트쇼에 당해버림.

질문 게시판보니까 나같은 사람이 많아보였다.

풀고보니 어제 풀었던 문제보단 어려운 문제였던거 같다.