BOJ 1167 : 트리의 지름 [C++]

 

 

문제

 

문제를 읽고 생각난 건 두 가지였다.

1. 그래프
2. DFS

그래서 dfs를 구현하고, 전체 정점에 대해서 dfs를 수행했다가 시간 초과로 틀렸다.

입력 vertex의 범위가 2개에서 10만 개였기 때문에, 시간 초과는 당연했다.

 

한 50분 고민하고, 밥 먹으면서도 고민해도 딱히 좋은 방법이 떠오르지 않아 

'질문 검색' 탭에서 글을 보다가 이 글을 보고 해결했다.

처음에는 마지막 댓글을 보고도 갸우뚱 했는데, 조금 생각해보니 이해할 수 있었다.

1에서 X까지의 거리가 1에서 갈 수 있는 최대 거리 max_distance 라고 하자.
그렇다면 X에서 출발하면 1을 거쳐 다른 곳으로 또 이동이 가능하기 때문에 이는 max_distance 보다 크다.

 

라고 이해했다.

 

코드

#include <iostream>
#include <vector>

std::vector<std::pair<int, int>> edges[100001];
bool visited[100001] = {false, };

int max_dist = 0;
int max_vertex = 0;

void dfs(int start, int dist) {
    visited[start] = true;

    if (dist > max_dist) {
        max_dist = dist;
        max_vertex = start;
    }

    for (std::pair<int, int> info : edges[start]) {
        if (visited[info.first]) {
            continue;
        }

        dfs(info.first, dist + info.second);
    }
}

int main() {
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    std::ios::sync_with_stdio(false);

    int v = 0;
    std::cin >> v;

    for (int i = 0; i < v; i++) {
        int start = 0;
        std::cin >> start;
        int dest = 0, dist = 0;
        while (1) {
            std::cin >> dest;
            if (dest == -1) {
                break;
            }
            std::cin >> dist;
            edges[start].push_back({dest, dist});
        }
    }

    dfs(1, 0);

    for (int i = 1; i < v + 1; i++) {
        visited[i] = false;
    }

    dfs(max_vertex, 0);

    std::cout << max_dist << "\n";

    return 0;
}

 

'PS > BOJ' 카테고리의 다른 글

BOJ 1865 : 웜홀 [C++]  (0)	2022.11.11
BOJ 1238 : 파티 [C++]  (0)	2022.11.10
BOJ 1043 : 거짓말 [C++]  (0)	2022.10.31
BOJ 11725 : 트리의 부모 찾기 [C++]  (0)	2022.10.30
BOJ 17626 : Four Squares [C++]  (0)	2022.10.27