https://www.acmicpc.net/problem/1167
오랜만에 알고리즘 트리 문제를 풀어봤습니다. 이 문제는 트리에서 임의의 두 정점 사이의 가장 긴 거리를 출력하는 문제입니다.
입력의 경우 시작 정점(from)이 주어지고, 시작 정점과 연결된 정점(to)과 두 정점 사이의 거리(dist)를 입력으로 받습니다. 더불어 해당 정점에서 입력을 종료하려면 -1을 입력으로 받아야 합니다.
첫 번째로, 우선 임의의 정점에서 가장 거리가 먼 노드를 찾습니다. 그 다음, 찾은 노드를 시작 노드로 지정하고 DFS 탐색을 해주면 트리의 지름을 반환할 수 있게 됩니다. 가장 거리가 먼 노드의 위치를 찾는 부분을 찾고 시작 노드로 지정해 주는 부분만 제외하면, 기본적인 DFS 문제와 유사합니다.(임의의 정점과 연결된 노드를 하나씩 방문하여 값을 갱신해줌)
<코드>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int v, from, to, dist, now_node;
int res = 0;
vector<pair<int, int>> graph[100001];
bool visited[100001];
void dfs(int from, int dist)
{
visited[from] = true;
if (dist > res)
{
res = dist;
now_node = from;
}
for (int i = 0; i < graph[from].size(); i++)
{
int next_node = graph[from][i].first;
int next_dist = graph[from][i].second + dist;
if (!visited[next_node])
{
visited[next_node] = true;
dfs(next_node, next_dist);
visited[next_node] = false;
}
}
}
void findMaxDistanceNodeFromNodeOfFirst()
{
dfs(1, 0);
}
void initializeMaxDistanceAndVisitStatus()
{
memset(visited, false, sizeof(visited));
res = 0;
}
void input()
{
cin >> v;
for (int i = 0; i < v; i++)
{
cin >> from;
while (true)
{
cin >> to;
if (to == -1)
break;
cin >> dist;
graph[from].push_back({to, dist});
}
}
}
int getDiameterOfTree()
{
dfs(now_node, 0);
return res;
}
int main()
{
input();
findMaxDistanceNodeFromNodeOfFirst();
initializeMaxDistanceAndVisitStatus();
cout << getDiameterOfTree() << '\n';
}
'PS > 깊이 우선 탐색, 너비 우선 탐색[DFS, BFS]' 카테고리의 다른 글
[PS] 백준 1707 이분 그래프(c++) (0) | 2023.12.24 |
---|---|
[PS] 백준 1068 트리 (c++) (0) | 2023.06.08 |
백준 2206 벽 부수고 이동하기(c++) (1) | 2023.02.14 |
백준 16946 벽 부수고 이동하기(c++) (0) | 2023.02.14 |
백준 7569 토마토(c++) (0) | 2023.02.05 |