algorithm little bishops

kukuman

백트래킹을 이해 할 수 있는 좋은 문제였던것 같습니다
알고리즘에 집착하다보니 코드 가독성과 구조가 극악 입니다. ㅠㅠ 추후에 리팩토링 해야될듯 덜덜
- 재귀를 안쓰고 풀수도 있을거 같은데 ㅋ 될까요? ㅋ 담에 시도해봐야 될 듯
입출력 처리는 하지 않았습니다 ㅋ

JAVA

  import java.util.ArrayList;
  
  
  public class ChessBoard {
  	private int n;
  	private int checkCount = 0;
  	public ChessBoard(int n) {
  		this.n = n;
  	}
  	public boolean isAttachPos(int i, int j) {
  		int difWidth = Math.abs(i/n-j/n); //위아래차이
  		int iPos = (i%n);
  		int jPos = (j%n);
  		return iPos==(jPos+difWidth) ||  iPos==(jPos-difWidth);
  	}
  	public int getSafeCount(int k) {
  		int [] curData = new int[k];
  		checkCount = 0;
  		backTracking(curData, 0, k);
  		return checkCount;
  	}
  	 
  	private void backTracking(int [] curData , int k, int i){
  		if(k==i){
  			processSolution(curData);
  		}else{
  			Integer [] candidates = makeCandidates(curData,k,i);
  			k++;
  			for(int cadidate : candidates){
  				curData[k-1] = cadidate;
  				backTracking(curData, k, i);
  			}
  		}
  		
  	}
  	private Integer [] makeCandidates(int[] curData,int k, int i) {
  		ArrayList<Integer> candidates = new ArrayList<Integer>(i);
  		//처음 시작은 모든 값이 후보가 됨
  		if(k==0){
  			for(int j=0;j<n*n;j++){
  				candidates.add(j);
  			}
  		}
  		else{ //curData에 값이 있는 경우에는 기존값과 비교하여 값츨 찾음
  			//새로운 후보 는 이전 값보다 크고 기존의 데이터와 Attacking Pos가 되지 않으면 된다.
  			for(int j=curData[k-1];j<n*n;j++){
  				boolean allSafe = true;
  				for(int z=0;z<k;z++){
  					int comVal = curData[z];
  					if(isAttachPos(comVal, j)){
  						allSafe = false;
  						break;
  					}
  				}
  				if(allSafe){
  					candidates.add(j);
  				}
  			}
  		}
  		Integer [] a = new Integer[candidates.size()];
  		return (Integer [])candidates.toArray(a);
  	}
  	
  	private void processSolution(int[] curData) {
  		
  		checkCount ++;
  		/*StringBuilder builder = new StringBuilder();
  		for(int val : curData){
  			builder.append(val);
  			builder.append(" ");
  		}
  		System.out.println(builder.toString());*/
  	}
  
  }

TEST CASE

  import junit.framework.TestCase;
  
  
  public class BisopTestCase extends TestCase {
  	public void testIsAttackPos(){
  		/*
  		 * 012
  		 * 345
  		 * 678
  		 * 
  		 */
  		ChessBoard board = new ChessBoard(3);
  		assertTrue(board.isAttachPos(0,0));
  		assertFalse(board.isAttachPos(0,1));
  		assertFalse(board.isAttachPos(0,2));
  		assertFalse(board.isAttachPos(0,3));
  		assertTrue(board.isAttachPos(0,4));
  		assertFalse(board.isAttachPos(0,5));
  		assertFalse(board.isAttachPos(0,6));
  		assertFalse(board.isAttachPos(0,7));
  		assertTrue(board.isAttachPos(0,8));
  		assertTrue(board.isAttachPos(1,5));
  		assertTrue(board.isAttachPos(0,8));
  		assertTrue(board.isAttachPos(4,0));
  		assertTrue(board.isAttachPos(6,4));
  		assertTrue(board.isAttachPos(0,8));
  	}
  	
  	public void testSafeCount(){
  		ChessBoard board = new ChessBoard(4);
  		assertEquals(260, board.getSafeCount(4));
  		ChessBoard board2 = new ChessBoard(8);
  		assertEquals(5599888, board2.getSafeCount(6));
  	}
  	
  }

ParkPD

또 Time limit exceeded 가!!

뭔가 요령이 없는 걸까.. 냠..

  /* @JUDGE_ID:parkpd 110401 Cpp "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #include <iostream>
  #include <vector>
  #include <set>
  #include <string>
  #include <strstream>
  #include <algorithm>
  #include <map>
  #include <math.h>
  
  //#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
  {
  
  ///////////////////////////////////////////////////////////////
  // CLittleBishops
  class CLittleBishops
  {
  public:
  	CLittleBishops(int n, int b) : m_Size(n), m_Boards(m_Size * m_Size), m_Bishops(b), m_Result(0) 
  	{
  		for (int r = 0; r < 8; ++r)
  		{
  			for (int c = 0; c < 8; ++c)
  			{
  				m_Board[r][c] = false;
  			}
  		}
  	}
  	
  	int Result();
  	void Find(int nBishopIndex, int startPos);
  	bool CheckAndPutBishop(int nBishopIndex, int startPos);
  	void RemoveBishop(int pos);
  	void GetRowCol(int pos, int& r, int& c) const;
  
  protected:
  	const int m_Size;
  	const int m_Boards;
  	const int m_Bishops;
  	int m_Result;	
  	bool m_Board[8][8];
  };
  
  int CLittleBishops::Result()
  {
  	m_Result = 0;
  
  	for (int i = 0; i < m_Boards; ++i)
  	{
  		Find(1, i);
  	}
  
  	return m_Result;
  }
  
  void CLittleBishops::Find(int nBishopIndex, int startPos)
  {
  	if (!CheckAndPutBishop(nBishopIndex, startPos))
  	{
  		return;
  	}
  	
  	if (m_Bishops <= nBishopIndex)	// 다 찾았다.
  	{
  		++m_Result;
  	}
  	else	// startPos 에 비숍 하나 놓을 수 있었다. 나머지 케이스에 대해서 backtrack 한다.
  	{	
  		for (int i = startPos + 1; i < m_Boards; ++i)
  		{
  			Find(nBishopIndex + 1, i);
  		}
  	}
  			
  	// startPos 에 놓고 해 볼 거 다 해 봤다. 제거해주자.
  	RemoveBishop(startPos);
  }
  
  // nBishopIndex : 1 ~ m_Bishops 까지
  bool CLittleBishops::CheckAndPutBishop(int nBishopIndex, int startPos)
  {
  	if (m_Boards < startPos + (m_Bishops - nBishopIndex))		// 현재 위치 + 남은 비숍 갯수가 넘치면 return
  	{
  		return false;
  	}
  
  	int r, c;
  	GetRowCol(startPos, r, c);
  
  	if (m_Board[r][c])		// 이미 bishop 이 들어있다.
  	{
  		return false;
  	}
  
  	// 대각선 테스트.
  	int test_r, test_c;
  	//for (int i = -1; i <= 1; i += 2)	// 최적화 1 - 아래로 검사할 필요 없음.
  	{
  		for (int j = -1; j <= 1; j += 2)	
  		{
  			// 테스트 cursor 위치 초기화
  			test_r = r;
  			test_c = c;
  
  			while(1)
  			{
  				// 대각선으로 위치 이동
  				//test_r += i;
  				test_r -= 1;		// 최적화 1
  				test_c += j;
  
  				// 검사
  				if (IsInRange(test_r, 0, m_Size - 1) && IsInRange(test_c, 0, m_Size - 1))
  				{
  					if (m_Board[test_r][test_c])	// 대각선에 bishop 이 있다.
  					{
  						return false;
  					}
  				}
  				else
  				{
  					break;
  				}
  			}
  		}
  	}
  
  	m_Board[r][c] = true;
  
  	return true;
  }
  
  void CLittleBishops::RemoveBishop(int pos)
  {
  	int r, c;
  	GetRowCol(pos, r, c);
  	m_Board[r][c] = false;
  }
  
  void CLittleBishops::GetRowCol(int pos, int& r, int& c) const
  {
  	r = pos / m_Size;
  	c = pos - (r * m_Size);
  }
  
  ///////////////////////////////////////////////////////////////
  // CConsole
  class CConsole
  {
  public:
  	static void ConsoleTest(istream& input, ostream& output);
  };
  
  void CConsole::ConsoleTest(istream& input, ostream& output)
  {
  	int scenarioIndex = 1;
  
  	while (1)
  	{
  		int nSize = 0;
  		int nBishops = 0;
  	
  		input >> nSize >> nBishops;
  
  		if ((0 == nSize) && (0 == nBishops))
  		{
  			break;
  		}
  
  		CLittleBishops bishop(nSize, nBishops);
  		output << bishop.Result() << "\n";
  	}
  };
  
  }
  
  using namespace ATCode;
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	CConsole::ConsoleTest(cin, cout);
  
  	return 0;
  }
  
  #else
  
  // tests
  
  struct FixtureBase
  {
  	FixtureBase() : b_2_1(2, 1), b_2_2(2, 2), b_4_1(4, 1)
  	{
  	}
  
  	CLittleBishops b_2_1;
  	CLittleBishops b_2_2;
  	CLittleBishops b_4_1;
  
  	int r, c;
  	stringstream input;
  	stringstream output;
  };
  
  TEST_FIXTURE(FixtureBase, Result)
  {
  	CHECK_EQUAL(4, b_2_2.Result());
  	
  	CLittleBishops b_4_4(4, 4);
  	CHECK_EQUAL(260, b_4_4.Result());
  
  	CLittleBishops b_8_6(8, 6);
  	CHECK_EQUAL(5599888, b_8_6.Result());
  }
  
  TEST_FIXTURE(FixtureBase, GetRowCol)
  {
  	CHECK_EQUAL(4, b_2_1.Result());
  		
  	b_2_1.GetRowCol(1, r, c);
  	CHECK(r == 0 && c == 1);
  	b_2_1.GetRowCol(2, r, c);
  	CHECK(r == 1 && c == 0);
  
  	CHECK_EQUAL(16, b_4_1.Result());
  
  	b_4_1.GetRowCol(1, r, c);
  	CHECK(r == 0 && c == 1);
  	b_4_1.GetRowCol(5, r, c);
  	CHECK(r == 1 && c == 1);
  }
  
  // 0 : Bishop 위치
  // OO
  // XX
  TEST_FIXTURE(FixtureBase, CheckAndPutBishop1)
  {
  	CHECK(b_2_2.CheckAndPutBishop(1, 0));
  	CHECK(!b_2_2.CheckAndPutBishop(2, 0));
  	CHECK(b_2_2.CheckAndPutBishop(2, 1));
  	CHECK(!b_2_2.CheckAndPutBishop(2, 2));
  	CHECK(!b_2_2.CheckAndPutBishop(2, 3));
  }
  
  // XO
  // X0
  TEST_FIXTURE(FixtureBase, CheckAndPutBishop2)
  {
  	CHECK(b_2_2.CheckAndPutBishop(1, 1));
  	CHECK(!b_2_2.CheckAndPutBishop(2, 2));
  	CHECK(b_2_2.CheckAndPutBishop(2, 3));
  }
  
  TEST_FIXTURE(FixtureBase, ConsoleTest1)
  {
  	input << 
  		"4 4\n"
  		"0 0\n";
  	CConsole::ConsoleTest(input, output);
  	CHECK_EQUAL("260\n", output.str());
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

Outbreak

문제 요약

n by n의 체스판에 k개의 비숍이 서로 공격받지 않도록 놓는 방법의 수는?

문제 해결 中

결국 재귀를 이용한 백트래킹
비숍의 공격 가능은 간단한 수식 활용
- y - x = d
- y + x = d
중복을 제거하기 위해 체스판을 1차원 배열로 계산
8x8 64개가 최대므로 double 형 비트연산 사용

소감 中

졸리더라도 밤에 하고 잘 것.
아침에 하니 잘 안되네요 ^^;
걍 C#으로 할 걸.. 갑자기 submit 욕심이..
이제 집에서 출발하니 40분정도 지각이요~ 흐;

풀이 中''' =

    /* @JUDGE_ID:present 110801 Cpp "LittleBishops" */
    
    /* @BEGIN_OF_SOURCE_CODE */
    
    #include <iostream>
    #include <map>
    #include <vector>
    
    using namespace std;
    
    #define _TDD
    
    // 1. > 직선의 방정식으로 푼다.
    //		기울기는 1 과 -1
    //		즉, y = x + d  또는 y = -x + d
    //		즉, y - x = d 또는 y + x = d 두 가지 경우가 같지 않으면 됨.
    //		두 경우에 대해 d 가 다르면 킬하지 않으면 됨.
    
    // 2. > 2차원 좌표를 1차원으로 생각한다!
    //		체스판의 최대 크기가 8x8 이므로 64비트 double 형 사용
    //		비트셋 연산 활용
    
    namespace Solver
    {	
    	class Bishop
    	{
    	public:
    		Bishop(int x, int y) : X(x), Y(y){};
    
    		bool operator == ( Bishop const& rhs )
    		{					
    			return IsAttackable(X, Y, rhs.X, rhs.Y);			
    		}
    
    		static bool IsAttackable(int x1, int y1, int x2, int y2)
    		{
    			if( (y1-x1) == (y2-x2) || (y1-x1) == (y2+x2) )
    				return true;
    			
    			return false;
    		}
    
    	public:
    		int X, Y;
    
    	};
    
    	class Board
    	{
    	public:
    		Board(int n, int k) : w(n), h(n), max(k), result(0){}
    
    		int GetOneDimIndex( int x, int y)
    		{
    			return x*w + y;
    		}
    
    		int GetXFromOneDim( int index )
    		{
    			return index%w;
    		}
    
    		int GetYFromOneDim( int index )
    		{
    			return index/w;
    		}
    		
    		void SetBishops(double currentBoard, int cnt)
    		{	
    			if( cnt == max )
    			{			
    				result = result + 1;										
    				return;
    			}
    
    			// 64bit 연산 재귀
    				
    		}
    
    		int Find()
    		{		
    			result = 1;
    			return result;
    		}
    
    	private:
    		int w, h, max;
    	
    		// MastoJun 님이 만들어 놓은 BigNumber 사용하기
    		int result;
    	};
    	
    	int Execute( int n, int k )
    	{	
    		Board board( n, k );
    		return board.Find();	
    	}
    }
    
    namespace Runner
    {
    	void Execute(istream& in, ostream& out)
    	{
    		int n = 0, k = 0;
    
    		do
    		{
    			in >> n >> k;
    
    			out << Solver::Execute(n,k) << endl;
    		}		
    		while( n != 0 || k != 0 );		
    	}
    }
    
    
    #ifdef _TDD
    #include "UnitTest++.h"
    
    using Solver::Bishop;
    using Solver::Board;
    
    TEST( Attackable )
    {
    	CHECK_EQUAL( true, Bishop::IsAttackable(1,1, 1,1) );
    	CHECK_EQUAL( true, Bishop::IsAttackable(1,1, 2,2) );
    	CHECK_EQUAL( true, Bishop::IsAttackable(1,1, 3,3) );
    
    	CHECK_EQUAL( false, Bishop::IsAttackable(1,1, 4,3) );
    	CHECK_EQUAL( false, Bishop::IsAttackable(1,1, 1,4) );
    }
    
    TEST( AttackableOperator)
    {
    	Bishop bs(0,0);
    	Bishop bss(1,1);
    	Bishop bsss(2,1);
    
    	CHECK_EQUAL( true, bs == bs );
    	CHECK_EQUAL( true, bs == bss );
    	CHECK_EQUAL( false, bs == bsss );
    }
    
    TEST( BoardOperation)
    {
    
    
    }
    
    TEST( 2x2 )
    {
    	Board bd(2,2);
    	
    	CHECK_EQUAL( 4, bd.Find() );
    }
    
    #endif // _TDD
    
    
    int main()
    {
    
    #ifdef _TDD	
    	UnitTest::RunAllTests();
    #else
    	Runner::Execute(cin, cout);
    #endif // _TDD
    	return 0;
    
    }
    
    /* @END_OF_SOURCE_CODE */

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

algorithm little bishops

kukuman

ParkPD

Outbreak

문제 요약

문제 해결 中

소감 中

풀이 中''' =

Clone this wiki locally