algorithm bicoloring - andstudy/forge GitHub Wiki

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());
  	}
  }

algorithm bicoloring - andstudy/forge GitHub Wiki

CynicJJ

Bicoloring.vb

COLOR.vb

Vertex.vb

BiColoringTest.vb

Outbreak

문제 요약

문제 해결

풀이

ParkPD

Mastojun

문제 풀이

소스 코드

Kukuman

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️