[C언어 기출문제&풀이] 두 색으로 칠하기(Bicoloring)

평면 위에 지도가 있을 때, 각 영역을 인접한 다른 영역과 구분할 수 있게 서로 다른 색으로 칠하고자 한다면, 네가지 색만 있으면 된다는 4색 정리(four-color theorem)라는 것이 있다. 이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에 컴퓨터의 도움을 받아서 증명될 수 있었다. 여기에서는 조금 더 쉬운 문제를 풀면 된다. 어떤 그래프가 주어졌을 대 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색 또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자. 문제를 간단하게 하기 위해 그래프가 연결 그래프고, 무방향 그래프며, 자체 루프가 없다고(즉(x,x)같이 한 정점에서 출발해서 그 정점을 ㅗ바로 연결되는 모서리가 없다고) 가정하자.

입력:여러 테스트 케이스가 입력될 수 있다. 각 테스트 케이스의 첫째 줄에는 정점의 개수 n(1<n<200)이 입력된다. 각 정점에는 0부터n-1까지의 번호가 붙는다. 그 다음 줄에는 모서리의 개수 l이 입력된다. 그 밑으로 l개의 줄이 입력되며, 각 줄에는 모서리를 나타내는 두 개의 정점 번호가 들어있다. n자리에 0이 입력되면 입력이 끝난 것이며, 그 줄은 처리하지 않는다.

출력 : 입력도니 그래프가 두 색으로 칠할 수 있는 그래프인지 판단하고 아래 예와 나온 형식에 맞게 결과를 출력하라.

풀이: 주어진 그래프를 깊이 우선 탐색으로 순회하면서 이전 방문했던 정점과는 다른 색으로 칠한다. 만약 연결된 정점에 이미 색이 칠해져 있는데, 칠할 색과 다른 경우 bicoloring이 불가능하게 된다.

소스코드
#include <stdio.h>

#define MAXN 200

static int n, graph[MAXN][MAXN];
static int color[MAXN]; //color[i] = i번째 정점의 색
static int colorable; //bicoloring 가능 여부

int input()
{
 int i,j,l,a,b;
 scanf("%d",&n);
 if(n==0) 
  return 0;
 //그래프 초기화
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   graph[i][j]=0;

 scanf("%d",&l);
 for(i=0;i<l;i++)
 {
  scanf("%d %d",&a,&b);
  graph[a][b]=graph[b][a]=1; //무방향그래프이기 때문
 }
 return 1;
}

void dfs(int node,int c)
{
 int i;
 color[node] = c; //node의 색은 c로 지정
 for(i=0;i<n&&colorable;i++)
 {
  if(graph[node][i] == 0) //node와 i가 연결되어 있지 않을 때
   continue;

  if(color[i] == 0)
   dfs(i,c%2+1); //i번째 노드를 중심으로 다시 순회
  else
  {
   if(color[i] == c) // 색이 같을 때
   {
    colorable = 0; //bicoloring 불가능
    return;
   }
  }
 }
}

void main(void)
{
 int i;

 while(input())
 {
  for(i=0;i<n;i++)
   color[i] = 0;
  colorable = 1;
  dfs(0,1);

  if(colorable == 0)
   printf("NOT BICOLORABLE.\n");
  else
   printf("BICOLORABLE\n");
 }
}