[C++] 백준 1167, 1967 : 트리의 지름

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

1167번: 트리의 지름

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

1967번: 트리의 지름

 

 

이 문제 개인적으로 그냥 dfs만 쓰면 풀리는 문제이길래

쉽겠거니~ 하고 덤볐다가 혼났어서.. 풀어보면 좋은 문제일 듯

 

1967번과 1167의 다른점은 트리의 노드 개수 뿐이다.

(1967: 만개 / 1167: 십만개)

 

1967번을 DFS한 번(그러나 DFS 내에서 sort가 들어감…) 으로 풀고,

노드개수가 더 큰 1167에 도전했더니 시간초과가 나서…

 

인접행렬이 아니라 인접리스트를 사용한 DFS 한번이라 시간복잡도가 O(V+E) 라서

괜찮을 줄 알았는데 재귀함수 내에 sort까지 있어서 O(V+E)가 아니게 된다..

 

그래서 다음과 같이 일반 DFS를 두 번 돌려서 가장 먼 노드를 찾는 방법을 선택했다.

노드 십만개인 1167번의 경우는 해결하는 데 아이디어가 필요했지만

이 아이디어가 다른 더 어려운 문제 풀 때도 적용하기 좋은 것 같아서

기억하기 위해 저장해놓은거고,

 

노드 만개인 1967번의 경우는 void 아닌 return 값 있는 재귀함수인데,

그 재귀함수의 return 값이 더 깊이 들어간 재귀함수의 return값들로 이루어진..(더 넓게는 영향을 받는?)

이걸 뭐라고 그러지 아무튼 그런 문제 연습하기 좋았어서 기록해놓는다.

 

<1167 코드> (노드 십만개)

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> adj_list[100001];
bool visit[100001];
int far_node = -1;
int max_dis = -1;

void dfs(int here, int dis) {
	visit[here] = true;
	if (dis > max_dis) {
		max_dis = dis;
		far_node = here;
	}

	for (pair<int, int> p : adj_list[here]) {
		int next = p.first;
		if (!visit[next]) dfs(next, dis + p.second);
	}
}

int main() {
	int V;
	scanf("%d", &V);

	int n1;
	for(int i = 0; i<V; i++) {
		scanf("%d", &n1);
		int n2, w;
		while (true) {
			scanf("%d", &n2);
			if (n2 == -1) break;
			scanf("%d", &w);
			adj_list[n1].push_back({n2, w});
			adj_list[n2].push_back({n1, w});
		}
	}
	
	dfs(1, 0);
	for (int i = 1; i <= V; i++) {
		visit[i] = false;
	}
	dfs(far_node, 0);
	printf("%d", max_dis);
}

 

<1967 코드 > (노드 만개)

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

vector<pair<int, int>> adj_list[10001];
bool visit[10001];
int dia_max = 0;

int dfs(int here) {
  visit[here]=true;
    
  vector<int> dis;
  for(pair<int, int> p: adj_list[here]) {
    int next=p.first;
    if(!visit[next]) {
      dis.push_back(dfs(next)+p.second);
    }
  }
  if(dis.empty()) return 0;
    
  sort(dis.begin(), dis.end(), greater<>());
  if(dis.size()>=2) {
    dia_max=max(dia_max, dis[0]+dis[1]);
  }
  else {
    dia_max=max(dia_max, dis[0]);
  }
  return dis[0];
}

int main() {
    int N;
    scanf("%d", &N);

    int n1, n2, w;
    while(--N) {
      scanf("%d%d%d", &n1, &n2, &w);
      adj_list[n1].push_back({n2, w});
    }

    dfs(1);
    printf("%d", dia_max);
}