[백준]1167 - 트리의 지름 (DFS)

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

1167번: 트리의 지름

정점과 각 정점간의 거리가 주어졌을때

가장 긴 두 정점 사이의 거리를 구하는 문제

 

각 정점들을 시작점으로 dfs 탐색을 해 최대값을 구하면 쉽게 풀리지만, 

정점이 촤대 10만개라 시간 초과가 발생한다

 

-> a 점을 시작으로 최대거리와 그때의 도착점 b를 구하고

다시 b를 시작점으로 최대거리를 구했을때 도착점이 a면 해당 거리가 최대 거리가 된다

 

예제 입력

 

int N;
cin >> N;
v = vector<vector<pair<int,int>>>(N+1);
while (N--) {
    int n;
    cin >> n;
    int a, b;
    while (1) {
        cin >> a;
        if (a == -1) break;
        cin >> b;
        if (a > n) {
            v[n].push_back({ a,b });
            v[a].push_back({ n,b });

v[3]은 3번 점과 연결된 1번점과  4번점, 그리고 해당 점까지의 거리인 {1,2} {4,3}을 지니게 된다

 

int start = 1;
visit[start] = 1;
dfs(start);
while(1) {
    counts = 0;
    for (int j = 0; j < 100000; j++)
        visit[j] = 0;
    visit[maxa] = 1;
    dfs(maxa);
    if (maxa == start) {
        cout << answer;
        return 0;
    }
    start = maxa;
}

임의의 점 1을 기준으로 dfs를 돌리고 최대거리(answer)와 그떄의 도착점(maxa)를 구함

이후 maxa를 기준으로 다시 탐색을 돌려 도착점이 시작점이면 값을 출력,

아니면 start에 maxa를 넣고 다시 탐색

 

void dfs(int i) {
    for (int k = 0; k < v[i].size(); k++) {
        int node = v[i][k].first;
        int gap = v[i][k].second;

dfs 탐색

매개변수로 시작점을 받고

for문으로 시작점에 연결된 정점들과 거리를 node, gap에 저장

        if (visit[node] != 1) {
            visit[node] = 1;
            counts += gap;
            if (counts > answer) {
                maxa = node;
                answer = counts;
            }
            dfs(node);
            counts -= gap;
            visit[node] = 0;

방문하지 않은 정점이면

방문했단 표시를 하고 누적 거리에 +

누적거리가 answer보다 크면 answer를 해당 값으로 = 최대 누적거리가 answer에 저장

 

이후 dfs 탐색을 재귀적으로 반복

dfs() 아래의 코드는 dfs 탐색후 되돌아오는 것이므로 counts와 visit를 다시 원래대로

 

 

 

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

void dfs(int i);
int visit[100001];
int answer = -1;
int counts =  0;
int maxa;
vector<vector<pair<int, int>>> v;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    v = vector<vector<pair<int,int>>>(N+1);
    while (N--) {
        int n;
        cin >> n;
        int a, b;
        while (1) {
            cin >> a;
            if (a == -1) break;
            cin >> b;
            if (a > n) {
                v[n].push_back({ a,b });
                v[a].push_back({ n,b });
            }
        }
    }
    int start = 1;
    visit[start] = 1;
    dfs(start);
    while(1) {
        counts = 0;
        for (int j = 0; j < 100000; j++)
            visit[j] = 0;
        visit[maxa] = 1;
        dfs(maxa);
        if (maxa == start) {
            cout << answer;
            return 0;
        }
        start = maxa;
    }
    return 0;
}

void dfs(int i) {
    for (int k = 0; k < v[i].size(); k++) {
        int node = v[i][k].first;
        int gap = v[i][k].second;
        if (visit[node] != 1) {
            visit[node] = 1;
            counts += gap;
            if (counts > answer) {
                maxa = node;
                answer = counts;
            }
            dfs(node);
            counts -= gap;
            visit[node] = 0;
        }
        
    }
    
}

전체 코드