<백준 알고리즘> 1167번 DFS이용

백준 1167번

접근방법

1. 처음에는 플루이드-워셜 알고리즘으로 하면 가능할 거라 생각했는데 정점이 최대 100000이 되므로 이차 배열로 나타내면 메모리 초과가 발생해 다른 방법을 찾게 되었다.
2. dfs를 이용하여 방문한 노드는 재방문을 하지 않고 cost를 합해가며 최대 값을 찾고 방문하지 않은 노드에 대해서는 거기서 시작하여 같은 방식을 한다는 점이었다.

2-1. 근데 양방향이므로 이미 방문한 노드에 대해 중복하지 못하도록 하면 만약 다른 길을 거쳐 같은 노드로 오는 다른 경우의 cost합이 더 클 경우를 반영하지 못한다.
2-2. 2-1을 보완하기 위해 다른 방법을 쓰면 양방향이므로 무한 실행을 하게된다.

3. 잘 안풀려서 이상해서 생각해보니 트리의 지름이었다. 일반적인 그래프라고 생각하고 풀어서 잘 안풀리는 것 이었다.
   3-1. 이후 접근 방식은 정점1에서 시작해 최대 거리가 나오는 정점을 기록하고 다시 그 최대 길이 정점에서 dfs를 하여 나오는 거리가 최대 거리가 된다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int V;

bool isFirst;

vector<pair<int, int>>  graph[100001];


int isVisited[100001] = { 0 };

long long maxVal = -1e9;
int maxNode = -1;

void dfs(int src, long long  totalCost)
{
   
    if (isVisited[src] == 1)
        return;

    if (maxVal < totalCost)
    {
        maxVal = totalCost;
        maxNode = src;
    }


    isVisited[src] = 1;


    int size = graph[src].size();
    

    for (int i = 0; i < size; i++)
    {
        int curDst = graph[src][i].first;
        long long  curCost = graph[src][i].second;
        
        totalCost += curCost;

        dfs(curDst, totalCost);

        totalCost -= curCost;
    }
}

int main()
{
    cin >> V;



    for (int i = 0; i < V; i++)
    {
        isFirst = false;
        int src;

        cin >> src;

        queue<int> qq;

        while (1)
        {

            int num;
            cin >> num;

            if (num == -1)
                break;


            qq.push(num);


        }

        int size = qq.size() / 2;

        for (int j = 0; j < size; j++)
        {
            int n = qq.front();
            qq.pop();
            int cost = qq.front();
            qq.pop();

            graph[src].push_back({ n,cost });
  

        }

    }

    dfs(1, 0);
    memset(isVisited, 0, sizeof(isVisited));

    maxVal = -1;

    dfs(maxNode, 0);

    cout << maxVal;

    return 0;
}