Walking the Approximate Longest Path

출처 : 해커 랭크

난이도 : 어려움

알고리즘 : NP

 

 

Jenna는 큰 지도를 포함하는 컴퓨터 게임을 하고 있습니다. n도시는 순차적으로 번호가 매겨짐 1에게 n에 의해 연결되어 있습니다 m양방향 도로. 게임의 목표는 한 도시를 두 번 이상 방문하지 않고 최대한 많은 도시를 여행하는 것입니다. 플레이어가 더 많은 도시를 방문할수록 더 많은 점수를 획득합니다.

해커랜드 대학교에서 제나의 동기생으로 활동하는 그녀는 최적의 경로를 선택하는 데 도움을 요청합니다. 지도를 참고하여 제나가 점수를 최대화하는 경로를 찾도록 도와줄 수 있나요?

참고: 그녀는 두 개의 서로 다른 도시에서 경로를 시작하고 끝낼 수 있습니다.

입력 형식

첫 번째 줄에는 각각의 값을 설명하는 공백으로 구분된 두 개의 정수가 포함됩니다.(도시의 수)와(도로의 수).
각 노선 i의 m이후 줄에는 공백으로 구분된 두 개의 정수가 포함됩니다. xi그리고 yi도시 간 양방향 도로를 설명합니다. xi그리고yi.

지도 생성 알고리즘

지도를 나타내는 그래프는 다음과 같은 방식으로 무작위로 생성되었습니다.

1. 처음에는 그래프가 비어 있었습니다.
2. 순열p1,....,pn모든 사람들 중에서 무작위로 균일하게 선택되었습니다. n!순열.
3. 각각에 대하여i ∈ {1,....,n-}, 가장자리(pi,pi+1)그래프에 추가되었습니다.
4. 추가 m - n + 1모든 가능한 집합 중에서 가장자리가 균일하게 무작위로 선택되었습니다. m - n + 1단계 중에 추가된 모서리와 교차하지 않는 모서리 3.

제약 조건

• 1 ≤ n ≤10^4
• 1 ≤ m ≤ 10^5
• 1 ≤ xi,yi ≤ n
• 을 위한 30%테스트의 n ≤ 25 그리고 m ≤ 75.
• 을 위한 50%테스트의 n ≤ 100 그리고 m ≤ 500.
• 을 위한 70%테스트의 n ≤ 500 그리고 m ≤ 2500.
• 길이가 유효한 경로가 보장됩니다.항상 존재합니다.

득점

• 길이가 유효한 경로벌어들인다테스트 케이스의 사용 가능한 점수입니다. 총점은 다음 점수로 반올림됩니다..

출력 형식

다음 두 줄의 출력을 인쇄하세요.

1. 첫 번째 줄에는 단일 정수가 포함되어야 합니다.d, 경로의 길이를 나타냅니다.
2. 두 번째 줄에는 다음이 포함되어야 합니다.d제나가 각 도시를 방문한 순서대로 그녀의 이동 경로를 설명하는 공백으로 구분된 정수입니다.

샘플 입력 0

4 5 
3 1 
3 4 
2 4 
2 3 
4 1

샘플 출력 0

4 
1 4 2 3

설명 0

아래 다이어그램은 도시의 초기 지도, 만점을 받을 수 있는 최적 경로, 부분 점수를 받을 수 있는 대체 경로를 보여줍니다.

최적의 경로(중앙 이미지)에서 Jenna는 경로를 걷고 있습니다.1>4>2>3. 이 답변은 100%경로 길이가 최대 점수이기 때문에4, 는 와 같다n(즉, 그녀는 모든 도시를 정확히 한 번씩 방문할 수 있었습니다).

대체 경로(오른쪽 이미지)에서 Jenna는 경로를 걷고 있습니다.1>4>3~을 위한최대 점수의.

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

무방향 graph를 입력받아 최대한 많은 노드를 방문하는 방문 횟수와 노드의 방문 순서를 출력하는 문제

 

문제접근

첫번째 접근 : DFS, 백트래킹을 통해 최장거리 노드를 방문하는 경로를 탐색

예외 발생 : 타임 아웃

 

두번째 접근 : NP, DFS, 백트래킹

 - 입력받은 그래프를 방문가능 노드 개수에 따라 내림차순으로 정렬

 - 상위 10개의 시작 그래프 노드만 선정

 - DFS를 통해 노드 탐색

  - 최대 길이를 저장하는 전역변수를 하나 선언하여 현재 탐색하는 노드의 최대길이가 이전 탐색한 노드의 길이보다 길 경우 최대 길이를 수정하고 최적경로를 현재 탐색중인 경로로 변경합니다.

  - 가지치기를 통해 현재 이동할 수 있는 남은 노드와 현재 길이를 합친 값이 현재까지 계산된 최대 길이보다 작으면 추가 탐색을 진행하지 않습니다.(방문 처리 false => 다른 경로로 접근할 수 있기 때문)

  - 가지치기를 통해 현재 이동할 수 있는 남은 노드에서 실제 방문 가능한 노드의 수를 구하여 이전 가지치기와 동일하게 최대 길이보다 작으면 추가 탐색을 진행하지 않습니다. (방문 처리 false => 다른 경로로 접근할 수 있기 때문)

  - DFS 탐색을 통해 반복합니다.

 

 

static void Main(String[] args) 
    {
        string[] firstLine = Console.ReadLine().Split();
        int n = int.Parse(firstLine[0]);
        int m = int.Parse(firstLine[1]);
    
        List<int>[] graph = new List<int>[n + 1];
        for(int i = 1; i <= n; i++)
            graph[i] = new List<int>();
    
        for(int i = 0; i < m; i++)
        {
            string[] edge = Console.ReadLine().Split();
            int u = int.Parse(edge[0]);
            int v = int.Parse(edge[1]);
        
            graph[u].Add(v);
            graph[v].Add(u);
        }
    
        for(int i = 1; i <= n; i++)
        graph[i].Sort((a, b) => graph[b].Count.CompareTo(graph[a].Count));
    
        int maxLength = 0;
        int[] bestPath = new int[n + 1];
        int bestPathLength = 0;
    
        bool[] visited = new bool[n + 1];
        int[] currentPath = new int[n + 1];
    
        void DFS(int node, int pathLength)
        {
            // 방문처리 및 경로 추가
            visited[node] = true;
            currentPath[pathLength] = node;
            pathLength++;
        
            // 최대 길이 업데이트
            if(pathLength > maxLength)
            {
                maxLength = pathLength;
                bestPathLength = pathLength;
                Array.Copy(currentPath, bestPath, pathLength);
            }
        
            // 가지치기(최대값)
            int remainingNodes = n - pathLength;
            if(pathLength + remainingNodes <= maxLength) 
            {
                visited[node] = false;
                return;
            }
        
            // 가지치기(실제 사용 가능한 노드 수)
            int availableNext = 0;
            foreach(int next in graph[node])
            {
                if(!visited[next]) 
                {
                    availableNext++;
                    if(availableNext + pathLength > maxLength) break;
                }
            }
        
            if(pathLength + availableNext <= maxLength)
            {
                visited[node] = false;
                return;
            }
        
            foreach(int next in graph[node])
            {
                if(!visited[next])
                {
                    DFS(next, pathLength);
                }
            }
        
            visited[node] = false;
        }
    
        var startNodes = Enumerable.Range(1, n)
                               .OrderByDescending(i => graph[i].Count)
                               .Take(Math.Min(10, n));
    
        foreach(int start in startNodes)
        {
            DFS(start, 0);
        }
    
        Console.WriteLine(bestPathLength);
        for(int i = 0; i < bestPathLength; i++)
        {
            if(i > 0) Console.Write(" ");
            Console.Write(bestPath[i]);
        }
        Console.WriteLine();
    }