Skip to content

algorithm bicoloring

Jump to bottom
Jongbin Oh edited this page Jun 8, 2013 · 1 revision

CynicJJ

  • Vertex 는 NONE, BLUE, RED 3가지 상태를 가짐

  • Edge 는 2개의 Vertex index 로 이루어짐

    • 따로 클래스로 만들지는 않았음

  • !ProcessEdge() 에서 2개의 Vertex 색을 다르게 만든다

  • 숨겨진 제약사항 - Edge 처리 순서를 지켜야 한다

    • 낮은 번호의 Vertex 부터 처리 해야함

  • 리팩토링의 여지가 더 있으나 귀찮아서...

Bicoloring.vb

    Public Class Bicoloring
    
    	Private _vertexes As List(Of Vertex) = New List(Of Vertex)
    	Private _edges As List(Of List(Of Integer)) = New List(Of List(Of Integer))
    
    	Function GetVertex(ByVal index As Integer) As Vertex
    		Return _vertexes(index)
    	End Function
    
    	Sub SetupEdges(ByVal inputs As List(Of String))
    		_edges.Clear()
    
    		Dim separator() As Char = {" "c}
    
    		Dim edgeCount = Integer.Parse(inputs(1))
    		For i As Integer = 1 To edgeCount
    			Dim input() As String = inputs(i + 1).Split(separator, StringSplitOptions.RemoveEmptyEntries)
    
    			Dim first As Integer = Integer.Parse(input(0))
    			Dim second As Integer = Integer.Parse(input(1))
    
    			Dim edge As List(Of Integer) = New List(Of Integer)
    			edge.Add(Math.Min(first, second))
    			edge.Add(Math.Max(first, second))
    
    			_edges.Add(edge)
    		Next
    	End Sub
    
    	Function IsBicolorable(ByVal inputs As List(Of String)) As Boolean
    		Dim vertexCount As Integer = Integer.Parse(inputs(0))
    		SetupVertexes(vertexCount)
    
    		SetupEdges(inputs)
    
    		ProcessAllEdges(_edges)
    
    		Dim result As Boolean = IsBicolor(_edges)
    		Return result
    	End Function
    
    	Function IsBicolor(ByVal edges As List(Of List(Of Integer))) As Boolean
    		For Each edge As List(Of Integer) In edges
    			Dim first As Vertex = GetVertex(edge(0))
    			Dim second As Vertex = GetVertex(edge(1))
    
    			If first.Color = second.Color Then
    				Return False
    			ElseIf first.Color = COLOR.NONE Or second.Color = COLOR.NONE Then
    				Return False
    			End If
    		Next
    		Return True
    	End Function
    
    	Sub ProcessAllEdges(ByVal edges As List(Of List(Of Integer)))
    		For i As Integer = 0 To _edges.Count - 1
    			For Each edge As List(Of Integer) In edges
    				If edge(0) = i Then
    					ProcessEdge(GetVertex(edge(0)), GetVertex(edge(1)))
    				End If
    			Next
    		Next
    	End Sub
    
    	Sub SetupVertexes(ByVal count As Integer)
    		_vertexes.Clear()
    		For i As Integer = 1 To count
    			_vertexes.Add(New Vertex)
    		Next
    	End Sub
    
    	Function GetVertexCount() As Integer
    		Return _vertexes.Count
    	End Function
    
    	Sub ProcessEdge(ByVal first As Vertex, ByVal second As Vertex)
    		If first.Color = COLOR.RED And second.Color = COLOR.NONE Then
    			second.SetColor(COLOR.BLUE)
    		ElseIf first.Color = COLOR.BLUE And second.Color = COLOR.NONE Then
    			second.SetColor(COLOR.RED)
    		ElseIf first.Color = COLOR.NONE And second.Color = COLOR.RED Then
    			first.SetColor(COLOR.BLUE)
    		ElseIf first.Color = COLOR.NONE And second.Color = COLOR.BLUE Then
    			first.SetColor(COLOR.RED)
    		ElseIf first.Color = COLOR.NONE And second.Color = COLOR.NONE Then
    			first.SetColor(COLOR.BLUE)
    			second.SetColor(COLOR.RED)
    		End If
    	End Sub
    End Class

COLOR.vb

    Public Enum COLOR
    	NONE
    	BLUE
    	RED
    End Enum

Vertex.vb

    Public Class Vertex
    
    	Private _color As COLOR = Basic.COLOR.NONE
    	ReadOnly Property Color()
    		Get
    			Return _color
    		End Get
    	End Property
    
    	Sub SetColor(ByVal aColor As COLOR)
    		_color = aColor
    	End Sub
    End Class

BiColoringTest.vb

    <TestClass()> _
    Public Class BicoloringTest
    
    	Private _bicolor As Bicoloring = New Bicoloring
    	Private _inputs1 As List(Of String) = New List(Of String)
    	Private _inputs2 As List(Of String) = New List(Of String)
    	Private _inputs3 As List(Of String) = New List(Of String)
    
    	Public Sub New()
    		_inputs1.Add("3")
    		_inputs1.Add("3")
    		_inputs1.Add("0 1")
    		_inputs1.Add("1 2")
    		_inputs1.Add("2 0")
    
    		_inputs2.Add("9")
    		_inputs2.Add("8")
    		_inputs2.Add("0 1")
    		_inputs2.Add("0 2")
    		_inputs2.Add("0 3")
    		_inputs2.Add("0 4")
    		_inputs2.Add("0 5")
    		_inputs2.Add("0 6")
    		_inputs2.Add("0 7")
    		_inputs2.Add("0 8")
    
    		_inputs3.Add("4")
    		_inputs3.Add("3")
    		_inputs3.Add("0 2")
    		_inputs3.Add("2 1")
    		_inputs3.Add("3 0")
    	End Sub
    
    	<TestMethod()> _
    	Public Sub SetVertexCountTest()
    		_bicolor.SetupVertexes(3)
    		Assert.AreEqual(3, _bicolor.GetVertexCount())
    		_bicolor.SetupVertexes(9)
    		Assert.AreEqual(9, _bicolor.GetVertexCount())
    	End Sub
    
    	<TestMethod()> _
    	Public Sub ProcessEdgeTest()
    		_bicolor.SetupVertexes(2)
    		Dim first As Vertex = _bicolor.GetVertex(0)
    		Dim second As Vertex = _bicolor.GetVertex(1)
    		second.SetColor(COLOR.BLUE)
    
    		_bicolor.ProcessEdge(first, second)
    		Assert.AreEqual(COLOR.RED, first.Color)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub IsBicolorableTest()
    		Assert.IsFalse(_bicolor.IsBicolorable(_inputs1))
    		Assert.IsTrue(_bicolor.IsBicolorable(_inputs2))
    		Assert.IsTrue(_bicolor.IsBicolorable(_inputs3))
    	End Sub
    
    End Class

Outbreak

문제 요약

  • 2가지 색으로 노드를 칠 할 수 있는데 인접한 노드간에는 반드시 다른 색깔을 가져야 한다.
  • 2가지 색으로 모든 노드를 칠 할 수 있는가?

문제 해결

  • 검정, 흰색 두가지 색이라고 했을 때
    • 첫 노드를 검정으로 칠하고 인접노드를 하나씩 칠해감.
    • 첫 노드를 흰색으로 칠하고 인접노드를 하나씩 칠해감.
  • 위 두 가지를 시도하고 하나라도 되면 Bicoloring 가능

풀이

    전철에서 ㄱㄱ

ParkPD

  • 생각보다 시간이 걸리는군요. :(

      /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <string>
  #include <strstream>
  #include <algorithm>
  #include <map>
  
  //#define _UNIT_TEST
  
  using namespace std;
  
  namespace ATUtil
  {
  
  bool IsInRange(int value, int from, int to)
  {
  	return (from <= value) && (value <= to);
  }
  
  int ConvertToIndex(char c)
  {
  	if ('a' <= c && c <= 'z')
  	{
  		return c - 'a';
  	}
  	else
  	{
  		return -1;
  	}
  }
  
  char ConvertToChar(int i)
  {
  	return (char)i + 'a';
  }
  
  typedef map<int, int> IntDB;
  typedef vector<int> Ints;
  
  };
  
  using namespace ATUtil;
  
  #ifdef _UNIT_TEST
  
  #include "../UnitTest++/src/UnitTest++.h"
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  // code implement
  
  namespace ATCode
  {
  
  ///////////////////////////////////////////////////////////////
  // CBicoloring
  class CBicoloring
  {
  public:
  	enum
  	{
  		MAX_SIZE = 200
  	};
  
  	enum Color
  	{
  		EMPTY = 0,
  		RED = 1,
  		BLUE = 2,
  		INVALID
  	};
  
  	CBicoloring();
  	void SetVerticesNum(int num);
  	void Connect(int from, int to);
  	bool IsBicolorable();
  	bool _IsBicolorable(int from);
  	int GetAdjectiveVertex(int from, Ints& ints);
  	string Result();
  
  	struct Vertex
  	{
  		Vertex(int index) : m_Index(index), m_Color(EMPTY) {}
  		Color GetOppositeColor()
  		{
  			if (m_Color == RED)
  			{
  				return BLUE;
  			}
  			else if (m_Color == BLUE)
  			{
  				return RED;
  			}
  			else
  			{
  				//_ASSERT(0);
  				return INVALID;
  			}
  		}
  
  		int m_Index;
  		Color m_Color;
  	};
  
  	std::vector<Vertex> m_Vertex;
  	int m_nVertexNum;
  	bool m_GraphEdges[MAX_SIZE][MAX_SIZE];
  };
  
  CBicoloring::CBicoloring() : m_nVertexNum(0)
  {
  	for (int i = 0; i < MAX_SIZE; ++i)
  	{
  		for (int j = 0; j < MAX_SIZE; ++j)
  		{
  			m_GraphEdges[i][j] = false;
  		}
  	}
  }
  
  void CBicoloring::SetVerticesNum(int num)
  {
  	m_Vertex.reserve(num);
  	for (int i = 0; i < num; ++i)
  	{
  		m_Vertex.push_back(Vertex(i));
  	}
  
  	m_nVertexNum = num;
  }
  
  void CBicoloring::Connect(int from, int to)
  {
  	m_GraphEdges[from][to] = true;
  	m_GraphEdges[to][from] = true;
  }
  
  bool CBicoloring::IsBicolorable()
  {
  	// 전체 vertex 를 쭉 돌면서 starting 지점으로 삼고,
  	// 인접 vertex 색이 
  		// 안 칠해져 있다면, 나와 다른 색으로 칠하고,
  		// 다르면 통과
  		// 같으면 실패
  
  	Vertex& s = m_Vertex[0];
  	s.m_Color = BLUE;
  
  	return _IsBicolorable(0);
  }
  
  bool CBicoloring::_IsBicolorable(int from)
  {
  	Vertex& s = m_Vertex[from];
  
  	Ints adjectives;
  	GetAdjectiveVertex(from, adjectives);
  
  	bool ret = false;
  
  	for (size_t i = 0; i < adjectives.size(); ++i)
  	{
  		int to = adjectives[i];
  		Vertex& v = m_Vertex[to];
  
  		// 인접 vertex 색이 
  		if (EMPTY == v.m_Color)	// 안 칠해져 있다면, 나와 다른 색으로 칠하고,
  		{
  			v.m_Color = s.GetOppositeColor();
  			ret = _IsBicolorable(to);
  		}
  		else if (s.m_Color != v.m_Color)
  		{
  			// OK
  			ret = _IsBicolorable(to);
  		}
  		else	// 인접 vertex 가 나와 같은 색. 췟...
  		{
  			ret = false;
  		}
  
  		if (!ret)
  		{
  			return false;
  		}
  	}
  
  	return true;
  }
  
  int CBicoloring::GetAdjectiveVertex(int from, Ints& ints)
  {
  	for (int to = 0; to < m_nVertexNum; ++to)
  	{
  		// edge 연결되어 있고, 아직 확인 안 된 vertex 라면
  		if (m_GraphEdges[from][to] && (m_Vertex[to].m_Color == EMPTY))
  		{
  			ints.push_back(to);
  		}
  	}
  
  	return (int)ints.size();
  }
  
  string CBicoloring::Result()
  {
  	if (IsBicolorable())
  	{
  		return "BICOLORABLE.\n";
  	}
  	else
  	{
  		return "NOT BICOLORABLE.\n";
  	}
  }
  
  ///////////////////////////////////////////////////////////////
  // CConsole
  class CConsole
  {
  public:
  	static void ConsoleTest(istream& input, ostream& output);
  };
  
  void CConsole::ConsoleTest(istream& input, ostream& output)
  {
  	//ostrstream tempOutput;
  
  	while (1)
  	{
  		int vertices = 0;
  		input >> vertices;
  
  		if (0 == vertices)
  		{
  			break;
  		}
  
  		int edges = 0;
  		input >> edges;
  
  		CBicoloring s;
  		s.SetVerticesNum(vertices);
  
  		int from;
  		int to;
  		for (int i = 0; i < edges; ++i)
  		{
  			input >> from >> to;
  			s.Connect(from, to);
  		}
  
  		output << s.Result();
  
  		//tempOutput << ends;
  		//output << tempOutput.str();
  	}
  };
  
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureConsole
  {
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureConsole, ConsoleTest1)
  {
  	input << "3\n3\n0 1\n1 2\n2 0\n0\n";
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("NOT BICOLORABLE.\n", output.str());
  }
  
  TEST_FIXTURE(FixtureConsole, ConsoleTest2)
  {
  	input << "9\n8\n0 1\n0 2\n0 3\n0 4\n0 5\n0 6\n0 7\n0 8\n0\n";
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("BICOLORABLE.\n", output.str());
  }
  
  TEST_FIXTURE(FixtureConsole, ConsoleTest3)
  {
  	input << "3\n2\n0 1\n1 2\n0\n";
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("BICOLORABLE.\n", output.str());
  }
  
  TEST_FIXTURE(FixtureConsole, ConsoleTest4)
  {
  	input << "3\n2\n0 2\n2 1\n0\n";
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("BICOLORABLE.\n", output.str());
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

Mastojun

문제 풀이

  • 학부 2학년때 그래프 부분을 제대로 공부를 못해서인지 그래프가 두려워요.

  • 자료는 Array를 이용해서 표현하고, 최초 node를 검정색으로 칠하고 연결되어있는 node들을 찾아가며 색을 칠하다가 이전 node랑 같은색의 연결된 node를 발견하면 false를 돌려주도록 했습니다.

  • 이번엔 소스가 깔끔하지 못하게 나왔네요 ㅠ_ㅠ..

소스 코드

    #include <stdio.h>
    #define ever (;;)
    
    enum COLOR {NONE, BLACK, WHITE};
    
    struct node
    {
    	bool use;
    	int  color;
    	bool isLink[200];
    }Matrix[200];
    
    int n;
    
    void InputData()
    {
    	int l;
    	scanf("%d", &l);
    
    	for(int i = 0; i < n; i++ )
    	{
    		Matrix[i].color = NONE;
    		Matrix[i].use	= false;
    
    		for(int j = 0; j < n; j++ )
    		{
    			Matrix[i].isLink[j] = false;	
    		}
    	}
    
    	for(int i = 0; i < l; i++ )
    	{
    		int temp1, temp2;
    
    		scanf("%d %d", &temp1, &temp2);
    
    		Matrix[temp1].use = true;
    		Matrix[temp2].use = true;
    		Matrix[temp1].isLink[temp2] = true;
    		Matrix[temp2].isLink[temp1] = true;	
    	}
    }
    
    int GetNextColor(int color)
    {
    	color++;
    	if(color > WHITE) color = BLACK;
    
    	return color;
    }
    
    //////////////////////////////////////////////////////////////////////////
    // no에 연결된 node들에 색을 다른색으로 칠해주는 함수.,
    //  만약 node에 이미 색이 칠해져 있다면,. no의 색과 같으면 false리턴
    //////////////////////////////////////////////////////////////////////////
    bool FillColor(int no, int color)
    {
    	int nextColor = GetNextColor(color);
    	
    	for(int i = 0; i < n; i++ )
    	{
    		if( Matrix[no].isLink[i] )
    		{
    			if( Matrix[i].color  == color ) // 이미 색이 칠해져 있는데 같다면..
    			{
    				return false;
    			}
    			else if( Matrix[i].color == NONE ) // 색이 칠해져 있지 않다면..
    			{
    				Matrix[i].color = nextColor;	// no와 다른색을 칠하기
    
    				if( FillColor(i, nextColor) == false ) // i와 연결된 node들 탐색 시키기!
    				{
    					return false;
    				}
    			}
    		}
    	}
    
    	return true;
    }
    
    
    bool GetResult()
    {
    	for(int i = 0; i < n; i++ )
    	{
    		if( Matrix[i].use )
    		{
    			Matrix[i].color = BLACK;
    
    			return FillColor(i, BLACK);
    		}
    
    	}
    
    	return true;
    }
    
    int main()
    {
    
    	for ever
    	{
    		scanf("%d", &n);
    
    		if( n == 0 ) break;
    
    		InputData();
    		if( GetResult() == false )
    		{
    			printf("NOT ");
    		}
    
    		printf("BICOLORABLE.\n");
    	}
    
    	return 0;
    }

Kukuman

  • 배열 배열로 그래프를 처리했습니다

  • 소스

      public class Graph {
  	private int pointCount;
  	private boolean[][] nodes;
  	
  	private final int RED=1;
  	private final int BLUE=2;
  	public Graph(int pointCount) {
  		this.pointCount = pointCount;
  		nodes = new boolean[pointCount][pointCount];
  		for(int i=0;i<pointCount;i++){
  			for(int j=0;j<pointCount;j++){
  				nodes[i][j] = false;
  			}
  		}
  	}
  	public void insertNode(int fromPoint, int toPoint) {
  		nodes[fromPoint][toPoint] = true;
  		nodes[toPoint][fromPoint] = true;
  		
  	}
  	public boolean checkBio() {
  		//방문했으면 색갈번호가 설정되어 있음 아니면 0
  		int [] traveledPoint = new int[this.pointCount];
  		for(int i=0;i<pointCount;i++){
  			traveledPoint[i] = 0;
  		}
  		
  		for(int fromPoint=0;fromPoint<pointCount;fromPoint++){
  			for(int toPoint=0;toPoint<pointCount;toPoint++){
  				//자신과 자신의 검사이라면 skip
  				if(fromPoint==toPoint)
  					continue;
  				
  				//해당 노드가 mark 되어 있으면 검사 수행
  				if(nodes[fromPoint][toPoint]){
  					//만약 시작점의 색깔이 안칠해져 있으면  기본색으로 칠함
  					if(traveledPoint[fromPoint]==0){
  						traveledPoint[fromPoint] = RED;
  					}
  					//만약 종료점의 색깔이 안칠해져있으면 시작점과 반대색
  					if(traveledPoint[toPoint] ==0){
  						traveledPoint[toPoint] = traveledPoint[fromPoint] == RED? BLUE:RED;
  					}
  					
  					//종료점과 시작점의 색깔이 같은지 검사 만일 같다면 false리턴
  					if(traveledPoint[fromPoint] == traveledPoint[toPoint]){
  						return false;
  					}
  					
  				}
  			}
  		}
  		
  		return true;
  	}
  
  }

  • 테스트케이스

      import junit.framework.TestCase;
  
  
  public class GraphTestCase extends TestCase {
  	public void testInitGraph(){
  		Graph graph = new Graph(3);
  		graph.insertNode(0,1);
  		graph.insertNode(1,2);
  		graph.insertNode(2,0);
  		assertFalse(graph.checkBio());
  	}
  	public void testInitGraph2(){
  		Graph graph = new Graph(7);
  		graph.insertNode(0,1);
  		graph.insertNode(0,2);
  		graph.insertNode(0,3);
  		graph.insertNode(0,4);
  		graph.insertNode(0,5);
  		graph.insertNode(0,6);
  		assertTrue(graph.checkBio());
  	}
  }

Clone this wiki locally