import java.util.*;
public class mColoring {
private int n;
private int m;
private int W[][];
private int vcolor[];
mColoring(int count, int colornumber){
int i, j; // for loop
char isTrue;
Scanner sc = new Scanner(System.in);
n = count;
m = colornumber;
W = new int[n][n];
vcolor = new int[n];
vcolor[0] = 1;
for ( i = 1 ; i <= n ; i++ ){
for ( j = 1 ; j <= n ; j++ ){
W[i-1][j-1] = 0;
}
}
for ( i = 1 ; i <= n ; i++ ){
for ( j = i ; j <= n ; j++ ){
if ( j == i ) continue;
System.out.print(i + "노드와 " + j + "노드는 인접한가?(y/n)");
String input = sc.next();
isTrue = input.charAt(0);
if ( isTrue == 'y' ){
W[i-1][j-1] = 1;
W[j-1][i-1] = 1;
}
}
}
}
private boolean promising(int i){
int j = 0;
boolean stc = true;
while ( j < i && stc ){
if( W[i][j] == 1 && vcolor[i] == vcolor[j] ) stc = false;
j++;
}
return stc;
}
public void m_coloring(int i){
int color;
if ( promising(i) )
if ( i == n-1 ){
printColor();
}else{
for ( color = 1; color <= m ; color++ ){
vcolor[i+1] = color;
m_coloring(i+1);
}
}
}
public void printColor(){
System.out.println("\nAnswer");
for ( int j = 0 ; j < n ; j++ ){
System.out.println((j+1) + "번재 노드의 색은 : " + vcolor[j] );
}
}
public static void main(String[] args){
int color, n;
Scanner sc = new Scanner(System.in);
System.out.print("정점의 개수는 ? ");
n = sc.nextInt();
System.out.print("색깔의 개수는? ");
color = sc.nextInt();
mColoring c = new mColoring(n,color);
c.m_coloring(0);
}
}
그래프의 상태를 입력하면 답을 제시해준다. 답이 존재하지 않으면 아무것도 출력해주지 않는다.