Hamilton Path

문제

1개의 도시에서 시작해 n-1 개의 도로를 지나 모든 도시를 방문하려 한다

도시는 1번만 방문한다

roads[i] 의 j번째 문자가 Y 이면
도시 i 와 도시 j 를 연결하는 도로를 반드시 지나야 한다

존이 선택할수 있는 경로의 수를 1,000,000,007 로 나눈 나머지를 리턴

예시 입력

1)
"NYN",
"YNN",
"NNN"

2)
"NYYY",
"YNNN",
"YNNN",
"YNNN"

3)
"NYY",
"YNY",
"YYN"

4)
"NNNNNY",
"NNNNYN",
"NNNNYN",
"NNNNNN",
"NYYNNN",
"YNNNNN"

//// 2개 cycle 체크용

5)
"NYYNNN",
"YNYNNN",
"YYNNNN",
"NNNNYY",
"NNNYNY",
"NNNYYN"

예시 출력

4
0
0
24
0

생각의 변화

한 붓
지나는 건 ok, 돌아오면 중복

다 탐색하는건 x

Y 배치후 다른 경로 조합 수
음..

어디서 출발

돌아오면 안되고, 도시는 1번만 지나야 하기 때문에
Y 그룹은 항상 직선이 된다. 따라서 2가지 경우만 갖게 된다
( Y 그룹의 원소가 2 이상인 경우 )

Y 그룹의 원소가 1 이면 1, 곱셈이므로 무시

Y 그룹을 만들려면 중복검사를 하기 편리한 너비탐색을 수행

Y 그룹들을 확보하면 이후 계산은 다음과 같다

Y 그룹들을 배치하는 경우의 수 n!
2 이상 Y 그룹들의 갯수 m

n! x m

돌아오는 경로가 있으면 예외처리 필요

너비탐색 수행 전에, 각 원소마다 dfs 로 cycle 검색
발견되면 0 리턴

사이클은 아니지만, Y가 3개 있는 경우에 대해서도 처리가 필요하다

pseudo code

factorial(n)
    if n <= 1
        return 1
    return n * factorial(n-1)

dfs(int hop, int current, int finish, vector<string> roads, vector<bool> visited)
    if hop != 0  &&  current == finish
        if hop == 2    // edge
            return 0
        else           // cycle
            return 1

    ret = 0
    i = 0
    
    for (auto ch : roads[current])
        if ch == 'Y'  &&  visited[i] == false
            visited[i] = true
            ret += dfs(hop+1, i, finish, roads, visited)
        
        i++
    
    return ret
    
countPaths(roads)
    vector<vector<int>> groups
    
    n = roads.size()
    
    vector<bool> visited(n, false)
    
    for (i=0  i<n  i++)
        result = dfs(0, i, i, roads, visited)
        
        if (result > 0)
            return 0
            
    for (auto &road : roads)
        y_count = 0
        for (auto c : road)
            if (c == 'Y')
                y_count++
                
            if (y_count == 3)
                return 0
            
    visited.assign(n, false)
    
    for (i=0  i<n  i++)
        vector<int> currentgroup
        queue<int> q
        
        if (!visited[i])

            q.push(i)
            visited[i] = true
            currentgroup.push_back(i)
            
            while (!q.empty())
                e = q.front()
                q.pop()
                
                j = 0
                for (auto c : roads[e])
                    if (c == 'Y'  &&  visited[j] == false)
                        q.push(j)
                        currentgroup.push_back(j)
                        visited[j] = true
                        
                    j++

            groups.push_back(currentgroup)
            
    multiplier = 0
    
    for (i=0  i<groups.size()  i++)
        if (groups[i].size() >= 2)
            multiplier += 2
            
    return (factorial(groups.size()) * multiplier) % 1000000007