[알고리즘] 되추적 - m_Coloring 코드 (Back_Tracking - m_Coloring Code)

문제)

Description

교재와 강의자료를 참고하여 m-Coloring 문제를 해결하는 Algorithm 5.5의 구현은 완성하시오.

주어진 평면 그래프 G = (V, E)에 대해서

인접한 지역을 서로 다른 색으로 색칠하기 위해 필요한 최소 색의 수 m의 값과

해당하는 m의 값으로 색칠할 수 있는 경우의 수를 출력하시오.

단,그래프의 입력은 간선의 집합으로 주어지고,주어진 그래프는 평면 그래프라고 가정해도 된다.

Input

첫 줄에 정점의 수 n과 간선의 수 k가 주어진다.

둘째 줄부터 k개의 간선이 주어진다.

Output

첫째 줄에 색칠 가능한 최소의 m값을 출력한다.

둘째 줄에 해당 m값으로 색칠할 수 있는 경우의 수를 출력한다.

Sample Input 1

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

Sample Output 1

3
6

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4
24

코드)

#include <iostream>
#include <vector>


using namespace std;


int ver_num, edge_num, cnt, m;
vector<vector<int>> W;
vector<int> vcolor;


bool promising(int i){
    int j = 1;
    while (j < i){
        if (W[i][j] && (vcolor[i] == vcolor[j]))
            return false;
        j++;
    }
    return true;
}


void m_coloring(int i){
    if (promising(i)){
        if (i == ver_num)
            cnt++;
        else{
            for(int color = 1; color <= m; color++){
                vcolor[i + 1] = color;
                m_coloring(i + 1);
            }
        }
    }
}


int main(){
    cin >> ver_num >> edge_num;

    W.resize(ver_num + 1, vector<int>(ver_num + 1, 0));

    int i, j;
    for(int k = 0; k < edge_num; k++){
        cin >> i >> j;
        W[i][j] = 1;
        W[j][i] = 1;
    }

    vcolor.resize(ver_num + 1, 0);

    for(m = 1; m <= ver_num; m++){
        cnt = 0;
        m_coloring(0);
        if (cnt)
            break;
    }

    cout << m << '\n' << cnt << '\n';

    return 0;
}

파이썬으로 안 풀려서 cpp로 해결함

 

2번째 코드) 파이썬으로 해결함

def promising(i: int) -> bool:
    for j in range(1, i + 1):
        if W[i][j] and vcolor[i] == vcolor[j]:
            # 인접한데 색깔까지 같다면 False
            return False
    return True


def m_coloring(i: int, m: int) -> bool:
    if promising(i):
        # 유망하거나 i번째까지 이상이 없는 경우
        if i == ver_num:
            # 무사히 leaf node까지 도달했다면
            global flag
            global cnt
            flag = True
            cnt += 1
        else:
            for color in range(1, m + 1):
                # 1부터 m까지 색깔을 넣음
                vcolor[i + 1] = color
                m_coloring(i + 1, m)


if __name__ == "__main__":
    ver_num, edge_num = map(int, input().split())       # 점점과 간선의 수
    W = [[0] * (ver_num + 1) for _ in range(ver_num + 1)]       # 인접행렬
    for _ in range(edge_num):
        # 인접행렬 만듬
        i, j = map(int, input().split())
        W[i][j] = 1
        W[j][i] = 1

    vcolor = [0] * (ver_num + 1)        # 색깔의 집합

    for m in range(1, ver_num + 1):
        # 최소의 m값을 출력하는 것
        flag = False        # 기본적으로 False로 나둔 후 색깔 칠하기가 가능하면 True로 변경
        cnt = 0
        m_coloring(0, m)
        if flag:
            # flag가 True라는 것은 색깔 칠하기가 가능하다는 의미
            print(m)
            print(cnt)
            exit()