정올 그래프 칠하기, 좋은 수열

#include <stdio.h>

/*

첫 줄에 노드 수 N(1≤N≤12)와 색상 번호 M(1≤M≤12)가 주어진다.

출력

노드1부터의 칠해진 색상 번호 리스트를 출력한다.

불가능한 경우 -1을 출력한다.

입력 예시

4 3

0

1 0

1 1 0

0 1 1 0

출력 예시

1 2 3 1

*/

 

// 그래프칠하기
#include <stdio.h>
/*
4 3
0
1 0
1 1 0
0 1 1 0
*/
int N;//노드수
int M;//색상번호
int SOL[14];
int MAP[14][14];
int RET;

int check( int V, int color) // V : 위치 , V : 색상
{
 int i;
 for (i = 1; i <= N; i++)
 {
  if (MAP[V][i] && SOL[i] == color) return 1; //인접한 정점에 같은 색이 이미 칠해져있는지 점검한다.
 }
 return 0;
}
int flag;
int dfs(int V)  // V: 접점
{
 if (V > N) {
  return 1;
 }
 int j;
 for (j = 1; j <= M; j++)
 {
  if (check(V, j) == 1) continue;
  SOL[V] = j;
  if (dfs(V + 1) == 1) return 1;
  SOL[V] = 0;
 }
 return 0;
}
int main(void)
{
 scanf("%d %d", &N, &M);
 int i, j , tmp;
 for (i = 1; i <= N; i++)
 {
  for (j = 1; j <= i; j++)
  {
   scanf("%d", &tmp);
   MAP[i][j] = MAP[j][i] = tmp;
  }
 }

 RET = dfs(1);
 if (RET)
 {
  for (i = 1; i <= N; i++)
  {
   printf("%d ", SOL[i]);
  }

 }
 else
 {
  printf("-1");
 }
 return 0;

}

한편  이 문제는 "좋은 수열" 문제와도 굉장히 유사하다.

#include <stdio.h>

  

int N;

char a[80+10];

  

int flag;

  

int strncmp(const char *s1, const char *s2, unsigned int n)

{

      while(n--)

      {

            if(*s1 > *s2) return 1;

            else if(*s1 < *s2) return -1;

            else if(*s1 == 0) return 0;

            s1++;

            s2++;

      }

      return 0;

}

  

int Check(int s)

{

      int i, cnt;

  

      if(s == 0) return 1;

      else

      {

            cnt = ++s / 2;

            for(i=1 ; i<=cnt ; i++)

            {

                  if(strncmp(&a[s-i], &a[s-i*2], i) == 0) return 0;

            }

      }

      return 1;

}

  

void DFS(int s)

{

      char i;

      if(s >= N)

      {

            flag = 1;

      }




      for(i='1' ; i<='3' ; i++)

      {

            a[s] = i; // 여기가 다르다.!! 그래프 칠하기의 경우 색상을 넣을지 말지를 확인하고 넣었으나, 여기에선 일단 넣고 될때 까지 돌린다.

            if(Check(s) == 0) continue;

            DFS(s+1);

            if(flag==1) return;

      }

}

  

int main(void)

{

      

      scanf("%d",&N);

      DFS(0);

      printf("%s", a);

  

      return 0;

}