algorithm freckles - andstudy/forge GitHub Wiki

ParkPD

Presentation Error 가 나는군요. 무시하려고 노력중입니다. :(

Presentation Error 해결

// main 의 마지막 부분 수정
output << setprecision(2) << fixed << s.Solve();
output << "\n";
if (i < testCount-1)		// presentation error 가 나서 넣어준다.
{
     output << "\n";
}

각자 서로에게 edge 를 가지는 그래프에서 Minimum Spanning Tree 를 구한다고 생각하고, Prim Algorithm 을 생각하며 풀었습니다.

  /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <string>
  #include <algorithm>
  #include <map>
  #include <limits>
  #include <assert.h>
  #include <iomanip>
  #include <math.h>
  
  //#define _UNIT_TEST
  
  #ifdef _UNIT_TEST
  #include <Windows.h>
  #endif
  
  using namespace std;
  
  // Minimum Spanning Tree -> Prim Algorithm 을 생각하며 풀었음.
  
  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';
  	}
  
  #ifdef _UNIT_TEST
  	class CStopWatch
  	{
  	public:
  		CStopWatch()
  		{
  			m_StartTick = GetTickCount();		// gcc 에서 안 될 수 있으니까
  		}
  
  		~CStopWatch()
  		{
  			cout << "Time passed : " << GetTickCount() - m_StartTick << " milisec.\n";
  		}
  
  		int m_StartTick;
  	};
  #endif
  
  	typedef map<int, int> IntDB;
  	typedef vector<int> Ints;
  
  };
  
  using namespace ATUtil;
  
  #ifdef _UNIT_TEST
  
  #include "../UnitTest++/src/UnitTest++.h"
  
  #ifdef max
  #undef max
  #endif
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  // code implement
  
  namespace ATCode
  {
  	//////////////////////////////////////////////////////////////////////////
  	// CPos
  	class CFreckle
  	{
  	public:
  		CFreckle() : m_X(0.0), m_Y(0.0), m_Dist(numeric_limits<double>::max()), m_Checked(false) {}
  		void Set(double x, double y)
  		{
  			m_X = x;
  			m_Y = y;
  		}
  		double GetDistFrom(const CFreckle& s)
  		{
  			return sqrt(((m_X - s.m_X) * (m_X - s.m_X)) + ((m_Y - s.m_Y) * (m_Y - s.m_Y)));
  		}
  
  		double m_X;
  		double m_Y;
  		double m_Dist;
  		bool m_Checked;
  	};
  
  	//////////////////////////////////////////////////////////////////////////
  	// CFreckleSolver
  	class CFreckleSolver
  	{
  	public:
  		CFreckleSolver(int n) : m_Num(n), m_Index(0), m_Checked(0) {}
  		void Insert(double x, double y)
  		{
  			m_Freckles[m_Index++].Set(x, y);
  		}
  
  		double Solve()
  		{
  			assert(m_Num == m_Index);
  
  			double ret = 0.0;
  
  			// 시작점 지정
  			int s = 0;
  			m_Freckles[s].m_Dist = 0.0;		// 시작점 거리는 0.0
  
  			m_Checked = 0;
  			while (m_Checked + 1 < m_Num)
  			{
  				CFreckle& newAdded = m_Freckles[s];
  				newAdded.m_Checked = true;
  				m_Checked++;
  
  				// 나를 제외한 모든 노드와 거리 계산 
  				// -> 현재 Freckle 에 저장된 값보다 거리가 짧다면 갱신한다.
  
  				// newAdded 노드와의 인접 노드를 돌면서 거리를 갱신한다.
  				double dist = 0.0;
  				for (int i = 0; i < m_Num; ++i)
  				{
  					CFreckle& iNode = m_Freckles[i];
  					if (iNode.m_Checked)
  					{
  						continue;
  					}
  
  					dist = newAdded.GetDistFrom(iNode);
  					if (dist < iNode.m_Dist)
  					{
  						iNode.m_Dist = dist;
  					}
  				}
  
  				// 검사하지 않은 노드 중 가장 거리가 짧게 지정된 노드를 다음 노드로 선택
  				double minDist = numeric_limits<double>::max();
  				for (int i = 0; i < m_Num; ++i)
  				{
  					CFreckle& iNode = m_Freckles[i];
  					if ((!iNode.m_Checked) && (iNode.m_Dist < minDist))
  					{
  						minDist = iNode.m_Dist;
  						s = i;		// 다음 검사할 node 를 지정
  					}
  				}
  
  				ret += minDist;
  			}
  
  			return ret;
  		}
  
  		int m_Num;
  		int m_Index;
  		int m_Checked;
  		CFreckle m_Freckles[100];
  	};
  
  	///////////////////////////////////////////////////////////////
  	// CConsole
  	class CConsole
  	{
  	public:
  		static void ConsoleTest(istream& input, ostream& output);
  	};
  
  	void CConsole::ConsoleTest(istream& input, ostream& output)
  	{
  		int testCount = 0;
  		input >> testCount;
  
  		for (int i = 0; i < testCount; ++i)
  		{
  			int posNum = 0;
  			input >> posNum;
  
  			CFreckleSolver s(posNum);
  
  			double x, y;
  			for (int j = 0; j < posNum; ++j)
  			{
  				input >> x >> y;
  				s.Insert(x, y);
  			}
  
  			if (1 <= i)		// presentation error 가 나서 넣어준다.
  			{
  				output << "\n\n";
  			}
  			output << setprecision(2) << fixed << s.Solve();
  		}
  	};
  
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureBase
  {
  	FixtureBase()
  	{
  	}
  
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureBase, Solve)
  {
  	CFreckleSolver s(3);
  	s.Insert(1.0, 1.0);
  	s.Insert(2.0, 2.0);
  	s.Insert(2.0, 4.0);
  	CHECK_CLOSE(3.41, s.Solve(), 0.01);
  }
  
  TEST_FIXTURE(FixtureBase, ConsoleTest)
  {
  	input << 
  		"1\n"
  		"\n"
  		"3\n"
  		"1.0 1.0\n"
  		"2.0 2.0\n"
  		"2.0 4.0\n"
  		;
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("3.41", output.str());
  }
  
  TEST_FIXTURE(FixtureBase, ConsoleTest1)
  {
  	input << 
  		"2\n"
  		"\n"
  		"3\n"
  		"1.0 1.0\n"
  		"2.0 2.0\n"
  		"2.0 4.0\n"
  		"\n"
  		"3\n"
  		"1.0 1.0\n"
  		"2.0 2.0\n"
  		"2.0 4.0\n"
  		;
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("3.41\n\n3.41", output.str());
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

kukuman

Presentation error 나네요 OTL

모든 점 점들이 연결 될수 있다는 가정하에 프링 알고리즘으로 최소신장트리를 구해서 각 노드의 길이를 출력하도록 하였습니다.

  /*
   * Main.java
   *  java program model for www.programming-challenges.com
   */
  
  import java.io.IOException;
  import java.text.DecimalFormat;
  
  class Main implements Runnable{
      static String ReadLn(int maxLength){  // utility function to read from stdin,
                                            // Provided by Programming-challenges, edit for style only
          byte line[] = new byte [maxLength];
          int length = 0;
          int input = -1;
          try{
              while (length < maxLength){//Read untill maxlength
                  input = System.in.read();
                  if ((input < 0) || (input == '\n')) break; //or untill end of line ninput
                  line [length++] += input;
              }
  
              if ((input < 0) && (length == 0)) return null;  // eof
              return new String(line, 0, length);
          }catch (IOException e){
              return null;
          }
      }
  
      public static void main(String args[])  // entry point from OS
      {
          Main myWork = new Main();  // Construct the bootloader
          myWork.run();            // execute
      }
  
      public void run() {
      	int testCaseCount = Integer.parseInt( ReadLn(255).trim() );
      	for(int i=0;i<testCaseCount;i++){
      		ReadLn(255);
      		int pointCount = Integer.parseInt( ReadLn(255).trim() );
      		BackBoard board = new BackBoard(pointCount);
      		for(int j=0;j<pointCount;j++){
      			String line = ReadLn(255);
      			String [] split = line.split(" ");
      			double x = Double.parseDouble(split[0]);
      			double y = Double.parseDouble(split[1]);
      			board.add(new Point(x,y));
      		}
      		double result = board.getMinLengh();
      		DecimalFormat df =new DecimalFormat("###.##");
  
      		System.out.println(df.format( result));
      		System.out.println("");
      	}
      }
  }
  
  
  
  class BackBoard {
  	private int pointCount;
  	private Point [] points;
  	public BackBoard(int pointCount) {
  		points = new Point[pointCount];
  		pointCount = 0;
  	}
  	public void add(Point point) {
  		points[pointCount++] = point;
  	}
  	
  	public int getPointCount(){
  		return this.pointCount;
  	}
  	public double getMinLengh() {
  		boolean [] isVisited = new boolean[pointCount]; //방문 했는지 여부
  		double [] distance = new double[pointCount]; //각 정점의  방문한 그래프와 최소 거리
  		
  		for(int i=0;i<pointCount;i++){
  			isVisited[i] = false;
  			distance[i] = Double.MAX_VALUE;
  		}
  		
  		//시작은 첫번째 점부터
  		int curPointCursor = 0;
  		distance[curPointCursor] = 0; //시작점의 거리는 자기자신이므로 0
  		
  		while(isVisited[curPointCursor]== false){
  			isVisited[curPointCursor] = true;
  			//방문한 점과의 최소거리를 유지하기 위한 로직
  			for(int i=0;i<pointCount;i++){
  				double curDistance = points[curPointCursor].getDistance(points[i]);
  				//현재 선택된 점과의 거리가  기존에 계산된 값이 작다면 update
  				if(isVisited[i] == false && distance[i] > curDistance){
  					distance[i] = curDistance;
  				}
  			}
  			
  			double minDistance = Double.MAX_VALUE;
  			curPointCursor = 1;
  			//다음 순회할 점을 선택 하는 로직
  			for(int i=0;i<pointCount;i++){
  				//다음 순회점은 방문한 점과의 거리가 가장 가까운 항목이 선택 된다.
  				if(isVisited[i] == false && distance[i] < minDistance){
  					minDistance = distance[i];
  					curPointCursor = i;
  				}
  			}
  		}
  		
  		double  distSum = 0;
  		//각 선의 길이는 distanc 배열의 합과 같다.
  		for(int i=0;i<pointCount;i++){
  			distSum += distance[i];
  		}
  		return distSum;
  	}
  
  }
  
  class Point {
  	private double x;
  	private double y;
  
  	public Point(double x, double y) {
  		this.x = x;
  		this.y = y;
  	}
  
  	public double getDistance(Point point2) {
  		return  Math.sqrt( Math.pow(x-point2.x, 2) + Math.pow(y-point2.y, 2)) ;
  	}
  
  }

test Case

  public class FrecklesTestCase extends TestCase {
  	public void testAddPoint(){
  		BackBoard board = new BackBoard(3);
  		board.add(new Point(1.0,1.0));
  		board.add(new Point(2.0,2.0));
  		board.add(new Point(2.0,4.0));
  		assertEquals(3,board.getPointCount());
  	}
  	
  	public void testPointDistance(){
  		Point point1 = new Point(1.0,1.0);
  		Point point2 = new Point(2.0,2.0);
  		Point point3 = new Point(2.0,4.0);
  		assertEquals(Math.sqrt(2.0), point1.getDistance(point2));
  		assertEquals(2.0, point2.getDistance(point3	));
  	}
  	
  	public void testMinLengh(){
  		BackBoard board = new BackBoard(3);
  		board.add(new Point(1.0,1.0));
  		board.add(new Point(2.0,2.0));
  		board.add(new Point(2.0,4.0));
  		assertEquals("3.41", String.format("%.2f",  board.getMinLengh()));
  	}
  }

Outbreak

문제 요약

평면 xy 에 여러점이 있을 때, 이 점들을 모두 직선으로 잇는 최소 길이를 구하라

문제 해결

열린목록, 닫힌목록을 만듬
처음 시작 시 닫힌목록에 1개를 넣어두고 나머지는 열린 목록
- 닫힌목록의 점들과 최소 거리의 점을 열린목록에서 선택
- 선택 된 점을 닫힌목록에 추가. 열린목록에선 제거.
- 위 두 과정 반복
크루스칼 알고리즘 형태인 듯?

소감

예전에 풀어봤던 문제.. 이번주는 쉽게 한문제.. ㅋㅋ
예전 코드를 보니, 풀이 구조를 정형화 시키려고 노력했던 것 같지만..
scanf/printf 를 왜 쓰냐는 이야기를 들었던 기억이 나네요 어휴~

풀이

    #include <cstdio>
    #include <cmath>
    #include <ctime>
    #include <vector>
    #include <algorithm>
    #include <string>
    
    using namespace std;
    
    class InputStuff;
    class OutputStuff;
    
    typedef vector<InputStuff> INPUT;
    typedef vector<InputStuff>::iterator INPUTItr;
    
    typedef vector<OutputStuff> OUTPUT;
    typedef vector<OutputStuff>::iterator OUTPUTItr;
    
    void InputProc(INPUT& Inputs );
    void MainProc( const INPUT& Inputs, OUTPUT& Outputs );
    void OutputProc( const OUTPUT& Outputs );
    
    //-------------------------------------------------------------
    
    int main(int argc, char* argv[])
    {
    	int maxtestcase;
    	scanf( "%d", &maxtestcase );
    
    	while( maxtestcase > 0 )
    	{		
    		INPUT inputs;
    		OUTPUT outputs;
    
    		// 입력계
    		InputProc( inputs );
    
    		// 처리계
    		MainProc( inputs, outputs );
    
    		// 출력계
    		OutputProc( outputs );
    	
    		if( --maxtestcase > 0)
    	            printf("\n");
    	}
    
    	return 0;
    }
    
    //---------------------------------------------------------------
    class PosStuff
    {
    public:
    
    	PosStuff( float Dx = 0.f, float Dy = 0.f ) : X(Dx), Y(Dy){}
    	
    	PosStuff& operator()( float Dx, float Dy )
    	{
    		X = Dx;
    		Y = Dy;
    		return *this; 
    	}
    
    	// 두 노드간의 거리계산
    	float operator-(const PosStuff& Dst)
    	{		
    		float xx = abs(this->X-Dst.X);
    		float yy = abs(this->Y-Dst.Y);
    	
    		return sqrt(xx*xx + yy*yy);
    	}
    public:
    	float X;
    	float Y;
    };
    
    class InputStuff
    {
    public:
    	vector<PosStuff> Nodes;
    };
    
    class OutputStuff
    {
    public:
    	float Length;
    };
    
    
    void InputProc(INPUT& Inputs )
    {
    	int maxample;
    	scanf( "%d", &maxsample);
    
    	InputStuff stuff;
    
    	while( maxsample > 0 )
    	{
    		int input = 0;
    
    		PosStuff xy;
    
    		scanf("%f %f", &xy.X, &xy.Y );
    
    		stuff.Nodes.push_back( xy );
    	
    		maxsample--;
    	}
    
    	Inputs.push_back( stuff );
    }
    
    float FindSmallestCost( const vector<PosStuff>& Nodes )
    {
    	vector<PosStuff> Opend;
    	vector<PosStuff> Closed;
    
    	// 닫힌 목록과 열린 목록을 만들어준다.
    	Closed.push_back( Nodes.front() );
    	Opend.assign( Nodes.begin()+1, Nodes.end() );
    	
    	// 전체 비용
    	float total = 0.f;
    
    	while( true )
    	{
    		// 최소 비용
    		float min = 9999999.f;
    
    		// 최소 비용이 되는 열린 목록의 타겟 노드
    		int minnode = 0;
    
    		for( int i=0; i<Closed.size(); i++ )
    		{
    			for( int j=0; j<Opend.size(); j++ )
    			{
    				// 열린 목록 중 최소 비용이 드는 노드를 찾는다.
    				float dist = Closed[i]-Opend[j];
    				if( min > dist )
    				{
    					min = dist;
    					minnode = j;
    				}
    			}
    		}
    
    		// 닫힌 목록에 삽입
    		Closed.push_back( Opend[minnode] );
    
    		// 열린 목록에서는 삭제
    		Opend.erase( Opend.begin() + minnode );
    
    		//printf("최소비용 노드는 %d 번째이고 비용은 %f \n", minnode, min);
    		total += min;
    
    		if( Opend.empty() )
    		{
    			//printf("모두 닫힌 노드가 됐습니다! 소비 비용은 %0.2f 입니다!\n", total);
    			break;
    		}
    	}
    	
    	return total;
    }
    
    void MainProc( const INPUT& Inputs, OUTPUT& Outputs )
    {	
    	for( int i=0; i<Inputs.size(); i++ )
    	{
    		vector<PosStuff> nodes;
    
    		nodes.assign( Inputs[i].Nodes.begin(), Inputs[i].Nodes.end() );
    
    		OutputStuff stuff;
    		stuff.Length = FindSmallestCost( nodes );
    
    		Outputs.push_back( stuff );
    	}
    }
    
    void OutputProc( const OUTPUT& Outputs )
    {
    	for( int i=0; i<Outputs.size(); i++ )
    	{		
    		printf( "%0.2f\n", Outputs[i].Length );
    	}	
    }

CynicJJ

준석씨 풀이와 같음

Point.vb

    Public Class Point
    
    	Sub New(ByVal x As Double, ByVal y As Double)
    		_x = x
    		_y = y
    	End Sub
    
    	Private _x As Double
    	Private _y As Double
    
    	ReadOnly Property x() As Double
    		Get
    			Return _x
    		End Get
    	End Property
    
    	ReadOnly Property y() As Double
    		Get
    			Return _y
    		End Get
    	End Property
    
    End Class

Freckles.vb

    Public Class Freckles
    
    	Shared Function GetDistance(ByVal p1 As Point, ByVal p2 As Point) As Double
    		Dim xDiff As Double = p1.x - p2.x
    		Dim yDiff As Double = p1.y - p2.y
    
    		Return Math.Sqrt(Math.Pow(xDiff, 2) + Math.Pow(yDiff, 2))
    	End Function
    
    	Shared Function FormatNumber(ByVal number As Double, ByVal digitsAfterDot As Integer) As Double
    		Dim strNumber As String = Microsoft.VisualBasic.FormatNumber(number, digitsAfterDot)
    		Return Double.Parse(strNumber)
    	End Function
    
    	Shared Function GetDistanceSum(ByVal points As List(Of Point)) As Double
    		Dim copied(points.Count - 1) As Point
    		points.CopyTo(copied)
    		Dim freckles As List(Of Point) = New List(Of Point)(copied)
    
    		Dim distanceSum As Double = 0
    
    		Dim checked As List(Of Point) = New List(Of Point)
    		checked.Add(freckles(0))
    		freckles.RemoveAt(0)
    
    		While freckles.Count > 0
    			Dim minDistance As Double = Double.MaxValue
    			Dim indexOfMin As Integer
    			For Each aChecked As Point In checked
    				For i As Integer = 0 To freckles.Count - 1
    					Dim distance As Double = GetDistance(aChecked, freckles(i))
    					If distance < minDistance Then
    						minDistance = distance
    						indexOfMin = i
    					End If
    				Next
    			Next
    
    			checked.Add(freckles(indexOfMin))
    			freckles.RemoveAt(indexOfMin)
    
    			distanceSum += minDistance
    		End While
    
    		Return FormatNumber(distanceSum, 2)
    	End Function
    
    End Class

!FrecklesTest.vb

    <TestClass()> _
    Public Class FrecklesTest
    
    	Private _points As List(Of Point) = New List(Of Point)
    
    	Sub New()
    		_points.Add(New Point(1.0, 1.0))
    		_points.Add(New Point(2.0, 2.0))
    		_points.Add(New Point(2.0, 4.0))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub FormatNumberTest()
    		Assert.AreEqual(1.41, Freckles.FormatNumber(1.40834, 2))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetDistanceTest()
    		Dim p1 As Point = New Point(1.0, 1.0)
    		Dim p2 As Point = New Point(2.0, 2.0)
    
    		Dim distance As Double = Freckles.GetDistance(p1, p2)
    		Assert.AreEqual(1.41, Freckles.FormatNumber(distance, 2))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetDistanceSumTest()
    		Assert.AreEqual(3.41, Freckles.GetDistanceSum(_points))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetDistanceSumTestMore()
    		Dim points As List(Of Point) = New List(Of Point)
    		points.Add(New Point(1.0, 1.0))
    		points.Add(New Point(2.0, 1.0))
    		points.Add(New Point(1.0, 2.0))
    		points.Add(New Point(1.0, 3.0))
    
    		Assert.AreEqual(3.0, Freckles.GetDistanceSum(points))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetDistanceSumTestMoreMore()
    		Dim points As List(Of Point) = New List(Of Point)
    		points.Add(New Point(1.0, 1.0))
    		points.Add(New Point(2.0, 1.0))
    		points.Add(New Point(1.0, 5.0))
    		points.Add(New Point(2.0, 5.0))
    
    		Assert.AreEqual(6.0, Freckles.GetDistanceSum(points))
    	End Sub
    
    End Class

soomong

프림 알고리즘을 처음 접해보는바. 문제풀이보다는 프림 알고리즘의 이해를 위주로 작성하였습니다 ^^

  #include "stdafx.h"
  #include "math.h"
  
  #define _UNIT_TEST
  #define MAXV 100
  
  #define MAXINT 142		// sqrt(pow(0,2)+pow(100,2)) = 141.42
  
  typedef struct
  {
  	double x;
  	double y;
  }point;
  
  typedef struct
  {
  	point points[MAXV+1];
  	int numPoint;	/* 정점 개수 */
  }graph;
  
  class CFreckles
  {
  private:
  	graph g;
  
  public:
  	CFreckles();
  	void addPoint(double x, double y);
  	double prim();
  	double getDistance(point a, point b);
  
  };
  
  CFreckles::CFreckles()
  {
  	g.numPoint = 0;
  }
  
  void CFreckles::addPoint(double x, double y)
  {
  	g.points[g.numPoint].x = x;
  	g.points[g.numPoint].y = y;
  	g.numPoint++;
  }
  
  
  double CFreckles::getDistance(point a, point b)
  {
  	return sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2));
  }
  
  
  double CFreckles::prim()
  {
  	bool intree[MAXV];		/* 정점이 트리에 들어있는지 여부 */
  	double distance[MAXV];	/* 시작점으로부터의 거리 */
  	int curPoint;		/* 지금 처리할 정점 */
  	double tempDist;			
  	double resultDist = 0;
  	int i,j;
  
  	// 각종 정보를 저장할 배열 초기화
  	for( i=0; i< g.numPoint; i++)
  	{
  		intree[i] = false;
  		distance[i] = MAXINT;
  	}
  
  	distance[0] = MAXINT;
  	curPoint = 0;
  
  	// 시작 point 0 과 나머지 모든 point 들의 거리를 초기값으로.
  	for( i=1; i< g.numPoint; i++)
  	{
  		// point 0 과 point i 의 거리
  		distance[i] = getDistance(g.points[0],g.points[i]);
  	}
  
  	intree[0] = true;
  	curPoint = 1;
  
  	while(intree[curPoint] == false)
  	{
  
  		// point i 에 대하여
  		for( i=0; i< g.numPoint; i++)
  		{
  			// i 를 연결하는 선이 있는경우 continue
  			if( intree[i] == true )
  				continue;		
  			
  			// i 로부터 j 까지의 모든 선의 distance 체크
  			for( j=0; j< g.numPoint; j++)
  			{
  				// j 를 연결하는 선이 있는경우 continue
  				if( intree[j] == true )
  					continue;		
  
  				tempDist = getDistance(g.points[i],g.points[j]);
  
  				// 최소 distance 이고 같은 point 끼리 연결하는게 아닐경우 갱신
  				if( distance[j] > tempDist && i != j )
  				{
  					distance[j] = tempDist;
  				}
  			}
  
  			intree[i] = true;
  		}
  
  		curPoint++;
  
  	}
  
  	// 1부터가 유효한 distance
  	for(int i=1; i<g.numPoint; i++)
  	{
  		resultDist += distance[i];
  	}
  
  	return resultDist;
  }
  
  
  #if defined(_UNIT_TEST)
  #include "UnitTest++.h"
  
  
  struct ConstructorTest
  {
  
  	ConstructorTest() : cf()
  	{
  
  	}
  	CFreckles cf,cf2,cf3;
  	graph g,g1,g2,g3;
  	
  };
  
  TEST_FIXTURE( ConstructorTest, FrecklesTest )
  {
  		
  	/*1.0 1.0
  	  2.0 2.0
  	  2.0 4.0 */
  	cf.addPoint(1.0,1.0);
  	cf.addPoint(2.0,2.0);
  	cf.addPoint(2.0,4.0);
  	CHECK_EQUAL(3.41,cf.prim());
  
  	/* 1.0 1.0
  	   2.0 2.0
  	   2.0 4.0
  	   1.0 0.0 */
  	cf2.addPoint(1.0,1.0);
  	cf2.addPoint(2.0,2.0);
  	cf2.addPoint(2.0,4.0);
  	cf2.addPoint(1.0,0.0);
  	CHECK_EQUAL(4.41,cf2.prim());
  
  	/* 3.0 1.0
  	   1.0 2.0
  	   3.0 3.0
  	   2.0 4.0
  	   4.0 5.0 */
  	cf3.addPoint(3.0,1.0);
  	cf3.addPoint(1.0,2.0);
  	cf3.addPoint(3.0,3.0);
  	cf3.addPoint(2.0,4.0);
  	cf3.addPoint(4.0,5.0);
  	CHECK_EQUAL(7.87,cf3.prim());
  
  }
  
  TEST_FIXTURE( ConstructorTest,  getDistanceTest )
  {
  	g.points[0].x = 1.0;
  	g.points[0].y = 1.0;	
  
  	g.points[1].x = 2.0;
  	g.points[1].y = 2.0;
  
  	g.points[2].x = 2.0;
  	g.points[2].y = 4.0;	
  
  	g.points[3].x = 4.0;
  	g.points[3].y = 3.0;
  
  	CHECK_EQUAL(1.41,cf.getDistance(g.points[0],g.points[1]));
  	CHECK_EQUAL(2,cf.getDistance(g.points[1],g.points[2]));
  	CHECK_EQUAL(2.23,cf.getDistance(g.points[2],g.points[3]));
  
  	g.points[4].x = 0;
  	g.points[4].y = 0;
  	g.points[5].x = 100;
  	g.points[5].y = 100;
  
  	CHECK_EQUAL(141.42,cf.getDistance(g.points[4],g.points[5]));
  
  }
  
  int main(int argc, _TCHAR* argv[])
  {
     return UnitTest::RunAllTests();
  }
  
  #else
  
  int main(int argc, _TCHAR* argv[])
  {
  	return 0;
  }
  
  #endif

Mastojun

문제 풀이

대세는 프림 알고리즘! ^^;
그래프에서 사용하는 알고리즘들은 많이 미진합니다

소스

    #include <stdio.h>
    #include <math.h>
    
    struct point
    {
    	float x, y;
    };
    
    int	n;			///< 주근깨 개수
    point	points[101];		///< 각 주근깨
    float	Distance[101][101];	///< 각 주근깨와 다른 주근깨의 거리
    bool	isUse[101];		///< 사용중인지 기억
    
    void InputData()
    {
    	scanf("%d", &n);;
    
    	for(int i = 1; i <= n; i++ )
    	{
    		scanf("%f %f",&points[i].x, &points[i].y);
    	}
    }
    
    void ConstructTable()
    {
    	float tempDist;
    
    	for(int i = 1; i <= n; i++ )
    	{
    		for(int j = 1; j <= n; j++ )
    		{
    			if( i == j )
    			{
    				Distance[i][j] = 0;
    			}
    			else
    			{
    				tempDist = sqrt( pow(points[i].x - points[j].x, 2) + 
    						 pow(points[i].y - points[j].y, 2) );
    
    				Distance[i][j] = tempDist;
    			}
    		}
    
    		isUse[i] = false;
    	}
    }
    
    float ShortFreckles()
    {
    	int FrecklesPoint;
    	bool isInit = false;
    	float MinDist;
    
    	for( int i = 1; i <= n; i++ )
    	{
    		if( isUse[i] == false ) continue;
    
    		for( int j = 1; j <= n; j++ )
    		{
    			if( i == j ) continue;
    			if( isUse[j] ) continue;
    
    			if( isInit == false )
    			{
    				MinDist = Distance[i][j];
    				FrecklesPoint = j;
    				isInit = true;
    			}
    			else
    			{
    				if( MinDist > Distance[i][j])
    				{
    					MinDist = Distance[i][j];
    					FrecklesPoint = j;
    				}
    			}
    		}			
    	}
    
    	isUse[FrecklesPoint] = true;
    
    	return MinDist;
    }
    
    float GetResult()
    {
    	float result = 0;
    
    	isUse[1] = true;
    
    	for(int i = 2; i <= n; i++ )
    	{
    		result += ShortFreckles();
    	}
    
    	return result;
    }
    
    int main()
    {
    	int testcase;
    
    	scanf("%d", &testcase);
    
    	while( testcase --> 0 )
    	{
    		InputData();
    		ConstructTable();
    
    		printf("%.2f\n", GetResult());
    
    		if(testcase)putchar('\n');
    	}	
    
    
    	return 0;
    }