[TopCoder] HamiltonPath (해밀턴 패스)

한 나라에는 N개의 도시가 있으며, 0에서 N-1까지 번호가 매겨져 있다. 각각의 도시 쌍은 양방향 도로로 연결되어 있다.
존은 다음과 같은 규칙을 사용하여 전국을 여행할 계획입니다:
그는 정확히 N-1 도로를 여행한 후 한 도시에서 시작해서 다른 도시에서 끝나야 한다.
그는 각 도시를 정확히 한 번 방문해야 한다.
도로가 주어졌습니다. 도로의 i번째 요소의 j번째 문자가 'Y'라면, 그는 city i와 city j를 연결하는 도로를 여행해야 한다.
예를 들어, 3개의 도시가 있고 0과 1 사이의 도로를 이동하려는 경우 0->1->2, 1->0->2, 2->0->1->1->0의 네 가지 경로가 가능합니다. 0->2->1번과 1->2->0번 경로는 그가 0시와 1시 사이의 도로를 이동할 수 없게 하기 때문에 허용되지 않는다.
그가 선택할 수 있는 경로 수를 모듈로 1,000,000,007로 반환합니다.

Definition

Class:

 

HamiltonPath

Method:

 

countPaths

Parameters:

 

vector <string>

Returns:

 

int

Method signature:

 

int countPaths(vector <string> roads)

(be sure your method is public)

Examples

0)

{"NYN", "YNN", "NNN"}

Returns: 4

The example from the problem statement.

1)

{"NYYY", "YNNN", "YNNN", "YNNN"}

Returns: 0

It's impossible to travel all these roads while obeying the other rules.

2)

{"NYY", "YNY", "YYN"}

Returns: 0

This is also impossible.

3)

{"NNNNNY", "NNNNYN", "NNNNYN", "NNNNNN", "NYYNNN", "YNNNNN"}

Returns: 24

---

roads 요소에 Y라고 되어있는 도시들끼리 연결해서 그 경로를 반드시 지나야한다. 

 

다만 출발 순서 상관없다. 0 - 1 - 2 순서로 연결되있을 때 0 - 1 - 2 혹은 2 - 1 - 0 이렇게 지나기만 하면된다. 

 

다만 1 - 0 - 2 처럼 순서를 무시하고 지날 순 없다. 

 

roads에서 모든 도시들간의 연결을 구하고, 연결된 도시 없이 혼자 있는 도시들의 수도 구한다. 

 

연결된 도시(0-1-2)를 하나의 묶음으로 생각하고, 혼자 있는 도시들과 함께 

 

순열을 구한다. 

 

가령 예를 들어 0, 1, 2, 3, 4, 5, 6, 7 도시들의 연결관계가 아래와 같다고 하자.

 

0

 

1 - 2 - 3 

 

4 - 5

 

6 

 

7

 

여기서 1 - 2 - 3 를 한 묶음으로, 4 - 5를 한 묶음으로 생각하면 

 

전체 요소들은 총 5개가 계산된다. 다만 연결된 도시들은 스타트를 끊는 순서가 2가지가 있으므로 

 

연결 묶음 수에 따라 2배씩 해주면 전체 경로의 경우의 수가 계산된다. 

 

5! * 2 * 2

 

코드로 구현해보자. 

 

#include <vector>
#include <string>
using namespace std;

class HamiltonPath{
    public:
    int isVisited[50] = {0};

 

각 도시들의 방문 여부를 체크하는 배열을 선언한다. 

 

    bool isPossiblePath(string path){
        int cnt = 0;
        for(int i=0; i<path.length(); i++){
            if(path[i] == 'Y'){
                cnt++;
            }
        }
        if(cnt>2){
            return false;
        }
        return true;
    }

연결 정보에 대해서 한 도시가 한번에 다른 3개(이상의) 도시에 연결되면 경로 만드는 것이 불가하다.

 

따라서 연결 정보를 보고 경로 생성 가능 여부를 판단하는 함수를 만들어주었다. 

    vector<int> getPath(vector <string> roads, int n, vector<int> pathVec, int departure, int before){
        if(!isPossiblePath(roads[n])){
            vector<int> emptyVec;
            return emptyVec;
        }

 그리고 하나의 도시를 시작으로 이 도시와 연결된 모든 도시들의 벡터를 반환하는 함수를 만든다.

 

만들어지는 경로는 pathVec에 저장하고, 도시 연결의 가장 시작이 되는 도시 departure를 파라미터로 준다. 

 

그리고 경로 상의 이전 연결 노드 before 도 파라미터로 준다.

 

먼저 현재 위치 n을 기준으로 3개 이상 연결된 도시가 있는지 판단하고, 해당되면 빈 벡터를 반환한다. 

 

        isVisited[n] = 1;

그것이 아니라면 해당 도시 n을 방문했음을 표시하고 

 

        for(int i=0; i<roads.size(); i++){
            if(i==before){
                continue;
            }

전체 도시들을 순회하면서 이전 연결 노드를 순회하는 경우는 건너뛰도록 한다. 

            if(roads[n][i] == 'Y' && i == departure && before != -1 && before!=departure){
                // i가 최초노드가 아니고, 출발노드랑 직접 연결되지도 않았는데, 
                //chain의 출발노드와 연결되어 있으면 순환 경로이므로
                vector<int> emptyVec;
                // 빈 벡터를 반환한다.
                return emptyVec;
            }

연결 경로의 출발 노드일 경우 before를 -1로 설정해주는데, 현재 도시 n이 출발 노드가 아니면서 

 

연결 도시로 판단되는 요소가 출발 노드와 연결되어 있을 경우 순환 경로가 되어서 경로 생성이 불가하다. 

 

출발 노드 - 도착 노드 2개로 구성된 경로일 경우에는 이미 continue 하였기 때문에 위 경우는 반드시 중간 노드에서 

 

출발 노드와 연결되는 케이스이다. 경로 생성이 안되므로 빈 벡터를 반환한다. 

 

            if(roads[n][i] == 'Y'){
                //이전 노드 말고도 추가적인 연결 노드가 있으면
                pathVec.push_back(i);
                isVisited[i] = 1;
                //지금 이 노드를 벡터에 추가하고
                vector<int> givenPath = getPath(roads, i, pathVec ,departure, n);
                // 연결 노드를 추적한다.
                if(givenPath.size()!=0){
                    //반환된 벡터가 빈 벡터가 아니라면
                    // 가능한 경로이므로 
                    return givenPath;
                }
                else if(givenPath.size()==0){
                    // 반환받은게 빈 벡터(불가 경로)
                    vector<int> emptyVec;
                    return emptyVec;
                    // 똑같이 빈 벡터를 반환한다. 
                }

불가 케이스를 모두 통과하고, 연결 노드가 있으면 그 연결 노드를 경로 벡터에 추가하고 방문 기록을 남긴다. 

 

그리고 현재 노드(n)을 이전 노드로 설정하고 해당 연결 노드(i)에서 더 연결되는 경로를 찾기위해 재귀 함수를 호출한다. 

 

그렇게 반환된 벡터가 빈 벡터가 아닐 경우, 가능한 경로이므로 그 벡터를 반환한다. 

 

만약 빈 벡터가 반환된 경우에는 후에 탐색했을 때 불가능한 상황이 만들어졌다는 의미이므로 나 역시

 

빅 벡터를 반환한다. 

 

        pathVec.push_back(n);
        //for문 다 돌았는데도 return 안됐으면 끝 노드이므로 자신을 추가하고 반환한다.
        return pathVec;

for문을 다 돌았는데도 return이 안됐다는 것을 연결 노드가 없다는 것이다. 따라서 

 

다른 도시들과 연결되지 않은 혼자 있는 도시이므로 나 자신만을 경로에 포함하여 반환한다. 

 

아니면, 재귀 함수 호출에서 더 연결된 노드가 없는 경로의 끝을 담당하는 노드일 경우이다. 

 

 

    int factorial(int n){
        if(n<=1){
            return 1;
        }
        else{
            return n*factorial(n-1);
        }
    }

전체 경로 경우의 수 계산을 위해 팩토리얼 함수를 만들어준다. 

 

    int countPaths(vector <string> roads){
        int caseNum = 0;
        vector<int> pathVec;
        int isolationNum = 0;
        int connectedNum = 0;
        for(int i=0; i<roads.size(); i++){
            if(isVisited[i] == 0){
                int pathSize = getPath(roads, i, pathVec, i, -1).size();
                if(pathSize == 0){
                    return 0;
                }
                if(pathSize == 1){
                    isolationNum++;
                }
                else{
                    connectedNum++;
                }
            }
            else{
                continue;
            }
        }
        caseNum = factorial(isolationNum+connectedNum);
        for(int i=0; i<connectedNum; i++){
            caseNum *= 2;
        }
        return caseNum;
    }

방문 기록이 아직 없는 노드들을 순회하면서 각 경로를 구한다. 

 

구해진 경로가 0의 길이를 갖고 있다는 것은 경로 생성이 불가한 경우를 찾아낸 것이기 때문에 0을 최종 반환한다.

 

그것이 아니라면 독립된 도시의 개수와, 연결된 도시들의 각 묶음 수를 구한다. 

 

위에서 설명한대로 각 도시들의 묶음(독립/연결)을 팩토리얼하여 순열을 구하고, 

 

연결된 도시들의 묶음 개수만큼 2배씩 곱해준다. 

 

그렇게 전체 경로 케이스 수를 구할 수 있다.