[프로그래머스/C++] 가짜 해밀토니안 (월간 코드 챌린지 시즌1)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 가짜 해밀토니안 경로를 만들 때, 어떻게 경로가 형성되는지 잘 파악해야 풀 수 있는 문제다.

 

문제에서 알려주는 가짜 해밀토니안 경로를 한번 분석해보자

위 그림에서 같은 그래프지만 2번 노드에서 어디로 가는지에 따라 만들 수 있는 가짜 해밀토니안 경로가 달라진다.

 

4번으로 가게 되면, 더 이상 2번 경로로는 돌아오지 못한다.

대신 2번 분기점에서 다른 곳으로 빠지지 않고 다시 1번까지 돌아가면 4번 5번을 거쳐 해밀토니안 경로를 만들 수 있다.

 

만들어진 해밀토니안 경로를 보면 특정 노드와 연결된 노드는 최대 3개가 될 수 있다.  

 

여기서 연결된 노드들을 3경우로 나눌 수 있다.

 

1. 처음 들어오는 경우

2. 나갔다가 되돌아오는 경우

3. 아예 나가는 경우

 

여기서 1번과 3번은 같은 양상을 보인다.

중요한건 2번만 다르다는 점이다.

 

나갔다가 되돌아오는 경우는 위 그림에서 볼 수 있듯이, 중간 노드가 2개 이상의 노드와 연결될 수 없다.

(1->2->3->2->1 로 이동이 가능해도 1->2->3->2->4로 이동하면 1로 되돌아 올 수 없다.)

 

그러므로 특정 노드에서 나갔다가 다시 되돌아 오는 경우는 하위 노드의 깊이 만큼만 경로를 추가할 수 있는 것이다.

이렇게 특정 노드로 다시 돌아오는 경우를 Depth라고 하자.

 

그러면 가짜 해밀토니안 경로에서 한 노드와 연결된 노드 3개를 구분하면 Depth, Spread, Spread로 구분할 수 있다.

 

여기서 Spread는 다시 돌아오지 않고 퍼지는 경로다.

(1, 3번 경우)

 

 

아래 그림을 보며 Spread와 Depth에 대해 한번 더 짚고 넘어가자

 

그림을 보면 왜 1번과 3번이 비슷한 양상을 띄는지 알 수 있다.

 

그림에서 Spread인 노드들은 N번 노드에 처음 들어오거나, 마지막으로 나가는 경우로 다시 N노드로 돌아오지 않기 때문에 하위에 있는 노드가 다른 노드와 최대 3개 연결이 가능하다.

 

요약하면 Depth가 된 하위 노드들은 연결된 노드가 2개 이상일 수 없고, Spread인 하위 노드들은 연결된 노드가 최대 3개가 가능하다.

 

이를 이용하면 특정 노드에서 다른 노드로 갈 때 Spread 값과 Depth 값을 이용해 가장 긴 가짜 해밀토니안 경로를 구할 수 있게 된다.

 

 

 

이제 실제로 가장 긴 가짜 해밀토니안 경로를 탐색하는 방법을 생각해 보자.

 

특정 노드에서 최대 2개의 Spread와 1개의 Depth의 경로를 가질 수 있다는 사실을 알았으므로, 이를 이용해 재귀적으로 알고리즘을 구현했다.

 

이때, 매 경로마다 현재까지 탐색한 가장 긴 해밀토니안 경로가 얼마인지 계산하도록 코드를 구현했다.

위 그림은 알고리즘의 진행을 도식화한 그림이다.

 

0번 노드를 최상단 노드라고 생각하고 0번 노드에서 시작해 DFS로 탐색을 시작한다. 이후 leaf 노드에 도달하면 (1,1,1)을 return한다.

여기서 return은 (최대 depth, 최대 Spread 값, 하위 Spread 2개 합의 최대 값)이다.

 

0번 노드에서 출발해 6번 노드에 도달했을 때를 예로 들어 진행해 보자, 하위 노드는 7, 8, 12번 노드로 각 노드들의 spread값은 [1, 4, 4], depth값은 [1, 4, 3] 이다.

 

이 경우에 6번 노드의 상위 노드를 방문하지 않는 가장 긴 해밀토니안 경로는 (1+4+4+1)인 10이 된다.

[6번 노드+spread+spread+depth]

 

이후 6번 노드의 계산이 종료 됐으므로 상위 노드였던 1번 노드로 돌아간다.

 

1번 노드도 마찬가지로 계산하면, 상위노드인 0번 노드를 방문하지 않는 가장 긴 해밀토니안 경로는 (1+4+9)=14가 된다.

[1번 노드+spread+spread] 

 

마지막으로 0번 노드로 돌아가면 가장 긴 해밀토니안 경로는 최종적으로 (1+14)=15 가 된다.

[0번 노드+spread]

 

 

+ 하위 Spread 2개의 합을 계산하는 이유는 재귀와 DFS로 코드를 구현했기 때문이다.

 

재귀의 특성상 현재 노드가 Depth에 포함된 노드일 경우에 아래 그림처럼 반례가 생길 수 있기 때문이다. 

S 노드에서 시작 했기 때문에 1번 노드에서 spread는 2, 4 노드 Depth는 7번 노드로 가짜 해밀토니안 경로를 계산한다.

 

하지만, 9번 노드가 Depth인 경우가 실제로 가장 긴 가짜 해밀토니안 경로이기 때문에 현재 노드가 Depth인 경우를 고려해 Spread의 2개 합이 max인 경우를 return해 예외처리를 해주는 것이다.

 

 

​

[아이디어 정리]

1. 특정 노드와 최대 연결된 노드는 최대 3개이고, 이는 2개의 Spread, 1개의 Depth로 나눌 수 있다. (Spread는 뻗어나가는 경우, 뻗어져 들어오는 경우를 의미한다, Depth는 단순히 다시 되돌아 오는 경우를 의미한다.)
2. DFS와 재귀를 이용해 자식 노드가 Spread와 Depth인 경우의 최대값을 기록한다.
3. 재귀의 특성상 자식노드에 Depth가 아니라 상위 부분이 Depth일 수 있으므로 하위 노드가 Spread인 경우의 최대값을 return해 예외를 처리한다.
4. 최종적으로 계산된 가장 긴 가짜 해밀토니안 경로를 return 한다.

 

+ 내용을 정리하다가 생각난 풀이인데 DFS와 재귀대신 특정 노드가 가짜 해밀토니안 경로에 포함된 경우, 포함되지 않은 경우로 문제를 풀면 더 간단하게 코드를 구현했을 것 같다...

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int answer=1;

vector<int> DFS(int parNode, int nowNode, vector<vector<int>> &graph)
{
    vector<int> nv(3,1), tempV; //depth, Spread, 하위 Spread 2개 합
    vector<vector<int>> v;
    int childNode=0;
    int maxV3=1;
    for (int i=0; i<graph[nowNode].size(); i++)
    {
        childNode=graph[nowNode][i];
        if (childNode!=parNode)
        {
            v.push_back(DFS(nowNode,childNode, graph));
        }
    }
    
    if (!v.empty())
    {
        // v3값 계산
        sort(v.begin(),v.end(),[](vector<int>a,vector<int>b){
            return a[2]==b[2]?a[0]>b[0]:a[2]>b[2];
        });
        int maxDepth=0;
        int maxV2=v[0][2]; //max nv[2]값
        if (v.size()>2)
        {
            for (int i=2; i<v.size(); i++)
            {
                maxDepth=max(maxDepth,v[i][0]);
            }
            answer=max({answer,1+max(maxDepth,v[1][0])+v[0][2], 1+max(maxDepth,v[0][0])+v[1][2]});
        }
        else if (v.size()==2)
        {
            answer=max({answer,1+v[1][0]+v[0][2], 1+v[0][0]+v[1][2]});
        }
        else if (v.size()==1)
        {
            answer=max(answer,1+v[0][2]);
        }
        
        sort(v.begin(),v.end(),[](vector<int>a,vector<int>b){
            // 만약 개수가 같다면, depth가 깊은 것을 앞으로 : 계산의 편리를 위해
        return a[1]==b[1]?a[0]>b[0]:a[1]>b[1];
        });
        
        maxDepth=0;
        if (v.size()>2)
        {
            for (int i=3; i<v.size(); i++)
            {
                maxDepth=max(maxDepth,v[i][0]);
            }
            
            answer=max({answer,
                        1+max(maxDepth,v[2][0])+v[0][1]+v[1][1],
                        1+max(maxDepth,v[0][0])+v[1][1]+v[2][1],
                        1+max(maxDepth,v[1][0])+v[0][1]+v[2][1]});
            
            nv[0]=1+max({maxDepth,v[0][0], v[1][0], v[2][0]});
            nv[1]=1+max( max({maxDepth, v[0][0],v[2][0]}) + v[1][1],  max({maxDepth,v[1][0],v[2][0]}) +v[0][1]);
            nv[2]=max(maxV2+1, v[0][1]+v[1][1]+1);
            return nv;
        }
        else if (v.size()==2)
        {
            answer=max(answer, 1+v[0][1]+v[1][1]);
            
            nv[1]=1+max(v[0][0]+v[1][1],v[0][1]+v[1][0]);
            nv[0]=1+max(v[0][0],v[1][0]);
            nv[2]=max(maxV2+1, v[0][1]+v[1][1]+1);
            return nv;
        }
        else
        {
            nv[0]=1+v[0][0], nv[1]=1+v[0][1];
            answer=max(answer,nv[1]);
            nv[2]=max(maxV2+1, v[0][1]+1);
            return nv;
        }
    }
    return nv;        
}

int solution(vector<vector<int>> t) {
    vector<vector<int>>graph(200000); //최대 20만개
    for (int i=0; i<t.size(); i++)
        graph[t[i][0]].push_back(t[i][1]), graph[t[i][1]].push_back(t[i][0]);
    DFS(-1,t[0][0],graph);
    
    return answer;
}

 

---

오랜만에 LV5 문제를 풀었다

문제의 풀이를 생각하는데 30분, 구현하는데 30분, 오류찾는데 30분, 반례 찾는데 30분... 반례 해결하는데 30분;;;

풀이가 빠르게 떠올랐던 것 같은데 그래도 엄청 시간이 오래 걸렸다...

풀이의 내용을 블로그에 정리하는데 약 2시간 30분...ㅠㅠㅠ

 

당분간 LV5의 풀이는 미뤄둬야겠다

프로그래머스