문제 이해 단계
https://www.acmicpc.net/problem/1167
입력으로 트리의 정점 개수 V와 간선의 정보가 주어진다.
트리의 간선에는 가중치가 존재한다.
임의의 두 정점 사이의 거리 중, 가장 긴 것의 길이를 출력하는 문제
문제 접근 단계
문제 조건부터 살펴보면, 정점의 개수가 최대 100,000개다.
그렇다면 간선의 개수는 훨씬 더 많이 가능하다는 소리이다.
모든 정점을 일일이 하나씩 다 살펴보기에는 무리이다.
한 정점을 특정하여 찾는 방법밖에 없는 것 같다.
두 정점 사이의 길이가 가장 길어지려면?
트리에서 두 정점의 길이가 가장 길어지려면 어떻게 해야 할까?
당연히 한쪽 끝노드(리프 노드)에서
끝노드로 가는 것이 길이가 가장 길어질 것이다.
즉 우리가 우선적으로 찾아야 할 것은 리프 노드들이다.
하지만 그냥 봐서는 우리를 이걸 알 수가 없다.
그래서 이걸 DFS를 한번 실행하면 이를 특정할 수 있다.
이게 무슨 소리일까? 밑에서 한번 예제를 보자.
해당 그래프에서 지름을 구하려면 어느 노드부터 시작하는 게 가장 유리할까?
우리를 그걸 알지 못하기 때문에 임의의 정점 하나를 잡도록 한다.
여기선 임의의 정점을 노드 3으로 하도록 하겠다.
노드 3을 시작점으로 거리가 가장 멀 때,
그러니까 얻을 수 있는 가중치의 합이 가장 클 때의 노드를 구한다.
DFS의 결과 노드 5에 도달했을 때 9로 가장 먼 거리를 가진다.
이때 노드 5는 리프노드가 된다.
지름 구하기
이제 리프노드를 구했기 때문에
노드 5를 출발 지점으로 하는 DFS를 하면, 길이가 가장 긴 지름의 길이를 구할 수 있게 된다.
DFS 결과로 예제 출력과 같은 11이 얻어진다.
최종 정리
결국 최종 정리하면 두줄로 요약된다.
1. 임의의 한 정점을 잡아 DFS를 돌려 리프노드를 구한다.
2. 찾은 리프노드로 다시 한번 DFS를 돌려 답을 구한다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int V;
vector<pair<int,int>> v[100001];
bool visited[100001] = {false,};
int selected; // 찾은 리프 노드
int dist = 0; // 답(최대 거리)
// dfs(현재 노드, 현재 거리)
void dfs(int x, int cnt){
// 현재 거리가 저장된 최대 길이보다 길다면,
// 리프 노드와 최대 길이값 갱신
if(dist < cnt){
selected = x;
dist = cnt;
}
// 일반적인 dfs
for(int i = 0; i < v[x].size(); i++){
int nx = v[x][i].first;
int cost = v[x][i].second;
if(!visited[nx]){
visited[nx] = true;
dfs(nx,cnt+cost);
visited[nx] = false;
}
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> V;
for(int i = 1; i <= V; i++){
int s, e, c;
cin >> s;
while(true){
cin >> e;
if(e == -1) break;
cin >> c;
v[s].push_back({e,c});
}
}
visited[1] = true;
dfs(1,0); // 임의의 노드를 무조건 노드 1로 잡음
fill(visited,visited+100001,false); // 방문 초기화
dist = 0; // 거리 초기화
visited[selected] = true;
dfs(selected,0); // 찾은 노드로 다시한번 dfs
cout << dist;
}dfs는 일반적인 dfs와 큰 차이점은 없다.
전역변수로 둔 dist와 selected가 있는데,
dist는 최대 길이를 의미하고, selected는 dfs로 선택된 노드를 의미한다.
dfs를 통해 cnt에 가중치 값을 더해주면서
dist와 비교, selected와 dist를 계속 갱신해 준다.
selected를 찾으면 visited배열과 dist를 초기화한 다음
찾은 selected노드를 출발점으로 하는 dfs를 다시 한번 돌려 답을 구한다.
설명은 여기까지이고 자세한 것은 주석을 참고하길 바란다.
시행착오
처음에는 크루스칼 알고리즘으로 풀었다가,
크루스칼 알고리즘은 모든 정점을 연결하는 최소/최대 비용을 만드는 법이라는 것을 까먹었다.
그다음에 사용한 방법은 리프 노드를 구하긴 하는 건데,
연결된 노드 개수를 통해 찾는 것이었다.
때문에 리프노드의 후보가 여러 개가 나왔다..
그래서 시간초과를 면하지 못했다..
그래서 1시간 안에 푸는 건 실패하고 결국 답을 찾아봤다.
DFS를 못 푸니까 좀 슬프다.
토스아이디
toss.me