문제 정의

그래프가 주어질 때 각 간선을 한번만 사용하여 만들 수 있는 가장 긴 경로의 길이를 구하라. (정점은 여러 번 방문할 수 있다.)

가장 긴 경로의 길이가 12인 그래프 예시

o      o--o      o
 \    /    \    /
  o--o      o--o
 /    \    /    \
o      o--o      o--o
           \    /
            o--o

아이디어

가장 긴 경로의 길이를 구하는 문제이므로, 모든 노드에서 DFS로 탐색하여 호출 때마다 경로의 길이를 증가시키면서 가장 긴 경로의 길이를 구하고자 하였다. 일반적인 DFS와 달리 이 문제에서는 정점을 여러 번 방문할 수 있고, 각 간선을 한번만 사용할 수 있으므로, 방문 여부를 기록하는 visited 변수는 각 간선마다 방문 여부를 저장하도록 하였다.

그래프와 동일하게 visited를 인접리스트로 저장하게 되면 같은 간선이 visited[from][to]와 visited[to][from]과 같이 두 군데 저장되게 되는데, 간선의 수가 최대 25개이므로, 각 간선의 visited를 갱신할 때마다 동일한 간선을 선형으로 찾아주어 두 군데를 동시에 갱신하도록 하였다.

일반적인 DFS의 시간복잡도가 $O(V+E)$이고, 이 문제에서는 각 경로를 갱신할 때마다 간선을 선형 탐색하므로 $E\times E$, 경로에 루프가 존재하면 정점을 두 번 방문하므로 $+ \alpha$, 모든 정점에 대해 DFS를 진행하므로 대략 $O(V(V+E^2+\alpha))=O(VE^2)$의 시간복잡도를 가질 것으로 보인다. 하지만 정점과 간선의 최대 개수가 25개이므로 제한 시간 안에 충분히 해결 가능하다.

풀이

각 테스트 케이스마다 정점과 간선을 받아 graph에 인접리스트로 저장한다. 그리고 각 정점마다 갖고 있는 간선의 크기만큼 visited를 초기화한다.

각각 정점에 대해 calcLongestPath 함수를 호출한다. 이 함수에서는 사용하지 않은 간선을 기준으로 깊이 우선 탐색을 진행한다. 호출의 깊이를 length 매개변수로 유지하면서 longestLength 전역 변수보다 커지면 longestLenght를 갱신하도록 하였다.

코드

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

int N, M, from, to;
vector<int> graph[25];
vector<bool> visited[25];
int longestLength;

int findSameEdge(vector<int> edges, int dest)
{
    for (int i = 0; i < edges.size(); i++) {
        if (edges[i] == dest)
            return i;
    }
}

void calcLongestPath(int now, int length)
{
    longestLength = max(longestLength, length);

    for (int i = 0; i < graph[now].size(); i++)
    {
        int dest = graph[now][i];
        if (!visited[now][i]) {
            visited[now][i] = visited[dest][findSameEdge(graph[dest], now)] = true;
            calcLongestPath(dest, length + 1);
            visited[now][i] = visited[dest][findSameEdge(graph[dest], now)] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    while (true)
    {
        longestLength = 0;

        cin >> N >> M;
        if (N == 0)
            break;

        for (int m = 0; m < M; m++) {
            cin >> from >> to;
            graph[from].push_back(to);
            graph[to].push_back(from);
        }
        
        for (int n = 0; n < N; n++)
            visited[n] = vector<bool>(graph[n].size(), false);
        
        for (int n = 0; n < N; n++)
            calcLongestPath(n, 0);

        int answer = longestLength;
        cout << answer << '\n';

        for (int i = 0; i < N; i++)
            graph[i].clear();
    }
    return 0;
}

결과