2814. 최장 경로

2814. 최장 경로

쉬운 문제라고 생각했는데, 결국 다른 사람의 힌트를 보고 나서야 풀 수 있었다..ㅠㅠ

그냥 단순히 각 정점을 돌면서 DFS를 돌리면 될거라고 생각했다..

하지만 만약 사이클이 생긴다면, 최장 거리가 달라질 수 있기 때문에 DFS에서 return 하기 전에 방문한 지점의 방문표시를 해제해줘야 했다..

생각이 짧아도 너무 짧았다..

아래 그림에서 

1->2->3->4->5 까지 방문을 먼저하고 3->7->6 이 되는 경우 최장거리는 5밖에 되지 않는다.

하지만 return 하면서 방문체크를 해제한다면

1->2->6->7->3->4->5 가 되기 때문에 최장거리가 7이 된다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int N, M, ans;
bool check[11];
void dfs(int now, int len, vector<vector<int>> &v)
{
    if (len>ans)
    {
        ans = len;
    }
 
    check[now] = true;
 
    for (int i = 0; i<v[now].size(); i++)
    {
        int next = v[now][i];
        if (!check[next])
        {
            dfs(next, len + 1, v);
        }
    }
    check[now]=false;
}
int main()
{
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        ans = 0;
        cin >> N >> M;
        vector<vector<int>> v(N + 1);
        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
 
        for (int i = 1; i <= N; i++)
        {
            memset(check, false, sizeof(check));
            dfs(i, 1, v);
        }
 
        cout << "#" << t << " " << ans << endl;
    }
    return 0;
}