[백준][bfs] 1967 트리의 지름 c++ 구현

목차

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

1967번: 트리의 지름

문제

 

 

 

 

문제 구현 방향

나는 리프 노드부터 bfs탐색을 시작하여 가중치를 더해준 후

그 중 가장 큰 가중치를 출력하는 방식으로 구현하였다.

가중치를 계속해서 누적해주는 것은 dp에서 착안하였다.

 

 

 

 

문제 풀이 시 주의할 점

그냥 인접행렬로 만들게 되면 메모리를 굉장히 많이 먹기 때문에 메모리 초과 오류에 빠진다.

따라서 구조체를 만들고 인접리스트를 사용하여 간선과 노드를 저장하는 방식으로 구현했다.

또한 가중치를 누적하는 배열 또한 1차원 배열로 출발점마다 재사용하여 메모리를 아껴주었다.

 

 

 

코드 구현

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

using namespace std;

struct Edge {     //구조체를 만들어 메모리 효율적으로 사용
	int to;     
	int weight;
	Edge(int t, int w) {
		to = t;
		weight = w;
	}
};
int n;
vector<int> d;     //이차원 배열로 만들면 메모리초과나옴 한번 사용하고 재사용
vector<Edge> tree[10001];   //메모리를 아끼기 위한 인접리스트 
//vector<int> tree[10001];  이 방식으로하면 미리 초기화를 해야해서 메모리 낭비가 남(인접 행렬이 됨)
vector<int> start_node;  //시작점 저장할 곳
vector<int> visit(10001, false);   

void bfs(int start) {
	int i, j;
    //bfs 시작시 초기화
	fill(visit.begin(), visit.end(), false);
	d.assign(10001, 0);
    
	queue<int>q;
	visit[start] = true;
	q.push(start);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (i = 0; i < tree[x].size(); i++) {
			int y = tree[x][i].to;
			if (!visit[y]) {
				q.push(y);
				visit[y] = true;
				d[y] = d[x] + tree[x][i].weight;    //dp와 유사한 방식으로 거리를 저장해 놓는다
			}
		}
	}

}
int main() {
	int node1, node2, w, i, j, maxD=0;
	cin >> n;
	for (i = 0; i < n - 1; i++) {  //트리이므로 양방향 연결리스트
		cin >> node1 >> node2 >> w;
		tree[node1].push_back(Edge(node2, w));
		tree[node2].push_back(Edge(node1, w));
	}
	for (i = 0; i <= n; i++) {   //배열의 사이즈가 1이면 리프노드이다
		if (tree[i].size() == 1) 
			start_node.push_back(i);
	}

	for (i = 0; i < start_node.size(); i++) {
		bfs(start_node[i]);    //리프 노드에서만 출발
	
		for(j=0; j<=n; j++)
		    maxD = max(d[j], maxD);  //최대값 갱신
	}

	cout << maxD;


}