백준 1967번 트리의 지름

문제 링크입니다: https://www.acmicpc.net/problem/1967

처음에는 DP로 접근하여 cache, graph는 MAX*MAX 크기로 잡고 visited는 MAX 크기로 잡으니 메모리 에러가 발생했습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000 + 1;

 

int N;

int graph[MAX][MAX];

bool visited[MAX];

int cache[MAX][MAX];

 

int getDiameter(int start, int node)

{

        int &result = cache[start][node];

        if (result != -1)

                 return result;

 

        result = 0;

        for (int i = 1; i <= N; i++)

                 if (graph[node][i] && !visited[i])

                 {

                         visited[i] = true;

                         result = max(result, graph[node][i] + getDiameter(start, i));

                         visited[i] = false;

                 }

        return result;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N - 1; i++)

        {

                 int node1, node2, diameter;

                 cin >> node1 >> node2 >> diameter;

                 graph[node1][node2] = diameter;

                 graph[node2][node1] = diameter;

        }

 

        memset(cache, -1, sizeof(cache));

 

        int result = 0;

        for (int i = 1; i <= N; i++)

        {

                 memset(visited, false, sizeof(visited));

                 visited[i]=true;

                 result = max(result, getDiameter(i, i));

        }

        cout << result << endl;

        return 0;

}

이후에는 DFS로 접근하여 cache를 사용하지 않아 메모리 여유공간이 충분하다고 생각했지만 마찬가지로 메모리 에러가 발생했습니다.

이에 따른 해결책으로 pair<int, int>형 벡터 배열을 만들어 트리 값을 입력 받으니 깔끔히 해결되었습니다.

알고리즘은 맞았는데도 메모리 에러가 발생하면 오답 처리가 되기 때문에 앞으로는 메모리에 신경을 써야겠습니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000 + 1;

 

int N;

bool visited[MAX]; //방문 여부

//int graph[MAX][MAX]; //서로 이어져있다면 해당 길이를 저장

vector<pair<int, int>> graph[MAX]; //메모리를 줄일 수 있다

 

int diameter = 0; //지름

int farthestNode = 0; //node 번호는 1번부터

 

void DFS(int node, int cost)

{

        //기저 사례: 이미 방문한 곳은 다시 방문 못함

        if (visited[node])

                 return;

 

        visited[node] = true;

 

        //지름 업데이트

        if (diameter < cost)

        {

                 diameter = cost;

                 farthestNode = node;

        }

 

        /*

        for (int i = 1; i <= N; i++)

                 if (graph[node][i])

                         DFS(i, cost + graph[node][i]);

        */

        for (int i = 0; i < graph[node].size(); i++)

                 DFS(graph[node][i].first, cost + graph[node][i].second);

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 1; i < N; i++)

        {

                 int node1, node2, cost;

                 cin >> node1 >> node2 >> cost;

 

                 //graph[node1][node2] = cost;

                 //graph[node2][node1] = cost;

                 graph[node1].push_back(make_pair(node2, cost));

                 graph[node2].push_back(make_pair(node1, cost));

        }

        memset(visited, false, sizeof(visited));

        //루트에서 가장 먼 정점 찾고

        DFS(1, 0);

        //해당 정점에서 가장 먼 정점까지의 거리가 트리 지름의 정해

        memset(visited, false, sizeof(visited));

        diameter = 0;

        DFS(farthestNode, 0);

       

        cout << diameter << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~