[=] 사석처리..

안녕하세요...

초보적인 질문좀 드리려고 합니다...

 

바둑에서 죽은돌을 들어내는 부분을 구현하려고 합니다.

전부터 여러가지 방법을 생각해 봤는데 제가 가진 지식으로는 힘이드네요..

 

한가지 가능성있는 방법을 간단히 설명해드리겠습니다..

이방법이 가능할지,문제점이 뭔지...그리고 다른방법은 없는지 답변 부탁드립니다..

 

...))

돌을 착점할때 돌의 연결을 관리하는 배열변수에 돌의넘버를 넣는것입니다.

1.돌을 착점할때 상하좌우로 체크해서 같은돌이 놓여있는지 확인

2.같은돌이 놓여있다면

      -1. 그 돌이 다른돌에 연결되어있는 돌인지 배열변수에서 확인한다

      -2. 그 돌이 다른돌에 연결되어있지 않다면 배열변수에 착점한돌과 연결된돌을 새로운 배열에 넣는다

      ex.그밖의 상황에 대해서는 내용이 길어질까봐 생략하겠습니다.

--여기까지가 돌의 연결을 관리하는 부분이 될텐데

   이렇게 하게 된다면 배열변수의 갯수가 몇개가 될지 모르고, 배열변수의 배열갯수가 몇개가 될지

   모른다는것이 문제입니다...배열변수의 갯수의 경우 한 20~30개 정도면 될거같은데..

   메모리를 많이 잡아먹지 않을까요?...

 

그리고 죽은돌을 들어내는것은 위의방법만 잘 코딩된다면 그리 어렵지 않을것 같습니다.

1.착점한돌이 백돌이면 흑돌이 상하좌우에 있는지 확인한다.

2.있다면 그 흑돌이 다른돌과 연결되어있는 배열변수에 포함되어있는지 확인한다.

3.포함되어 있다면 포함된 각각의 돌의 숨구멍의 갯수를 구한다.

   숨구멍이란 돌이 다른돌에 막혀있는지가 됩니다.

   예를들어서 각각의 돌이 상하좌우로 비어있다면 0, 막혀있다면 1, 로 해서 다 구한다음에

   0의 값을 가지고 있는 돌이 하나도 없다면 죽은돌로 판단. 그 배열변수에 포함된 돌을 제거.

   ex. 이거 역시 다른 세부적인 부분은 생략하겠습니다.


*

'배열변수' 라는게 뭘 뜻하는 건지는 모르겠지만 기본적인 알고리즘은 맞는거 같습니다. 바둑에서 사석을 체크하거나 들어내는 알고리즘은 페인터에서 쓰이는 폐곡선 내부를 채워주는 Flood Fill 알고리즘을 응용하시면 될겁니다. 일단 제가 예전에 만들다 만 프로그램 소스를 올려드립니다. 소스에는 안나와 있지만 m_Board[19][19] 배열이 바둑판이고 0은 빈공간, 1은 흑돌, 2는 백돌을 나타냅니다. BYTE xStone도 마찬가지고요. 제일 밑에 있는 void CBadukDoc::CheckDeadStone(int nX, int nY, BYTE xStone) 함수가 진입점입니다. 유저가 돌을 하나 놓았을때마다 돌의 위치와 색깔을 파라메터로 호출하면 그돌로 인해 사석이 생겼는지를 체크해서 실제로 없애주게 됩니다. CheckDeadStone -> IsDeadStone -> IsClosed (Recursive ) 로 사석이 생겼는지 판단하고 CheckDeadStone -> RemoveDeadStones -> RemoveStones (Recursive)로 실제 사석을 지웁니다. bool CBadukDoc::IsClosed(int nX, int nY, BYTE xStone, LPBYTE pxChecked) {     int nLeftX, nRightX;     if (m_Board[nY][nX] == 0)         return false;     else if (m_Board[nY][nX] != xStone)         return true;     else     {         pxChecked[nY * 19 + nX] = 1;         nLeftX = nX - 1;         while (nLeftX >= 0 && !pxChecked[nY * 19 + nLeftX])         {             pxChecked[nY * 19 + nLeftX] = 1;             if (m_Board[nY][nLeftX] == 0)                 return false;             else if (m_Board[nY][nLeftX] != xStone)                 break;             nLeftX--;         }         nLeftX++;         nRightX = nX + 1;         while (nRightX < 19 && !pxChecked[nY * 19 + nRightX])         {             pxChecked[nY * 19 + nRightX] = 1;             if (m_Board[nY][nRightX] == 0)                 return false;             else if (m_Board[nY][nRightX] != xStone)                 break;             nRightX++;         }         nRightX--;         for ( int i = nLeftX; i <= nRightX; i++ )         {             if ((nY > 0) && !pxChecked[(nY - 1) * 19 + i])             {                 if (!IsClosed(i, nY - 1, xStone, pxChecked))                     return false;             }             if ((nY < 19 - 1) && !pxChecked[(nY + 1) * 19 + i])             {                 if (!IsClosed(i, nY + 1, xStone, pxChecked))                     return false;             }         }         return true;     } } bool CBadukDoc::IsDeadStone(int nX, int nY, BYTE xStone) {     LPBYTE pxChecked = new BYTE[19 * 19];     ZeroMemory(pxChecked, 19 * 19);     bool bRet = IsClosed(nX, nY, xStone, pxChecked);     delete [] pxChecked;     return bRet; } void CBadukDoc::RemoveStones(int nX, int nY, BYTE xStone, LPBYTE pxChecked) {     int nLeftX, nRightX;     if (m_Board[nY][nX] != xStone)         return;     else     {         m_Board[nY][nX] = 0;         pxChecked[nY * 19 + nX] = 1;         nLeftX = nX - 1;         while (nLeftX >= 0 && !pxChecked[nY * 19 + nLeftX])         {             pxChecked[nY * 19 + nLeftX] = 1;             if (m_Board[nY][nLeftX] != xStone)                 break;             m_Board[nY][nLeftX] = 0;             nLeftX--;         }         nLeftX++;         nRightX = nX + 1;         while (nRightX < 19 && !pxChecked[nY * 19 + nRightX])         {             pxChecked[nY * 19 + nRightX] = 1;             if (m_Board[nY][nRightX] != xStone)                 break;             m_Board[nY][nRightX] = 0;             nRightX++;         }         nRightX--;         for ( int i = nLeftX; i <= nRightX; i++ )         {             if ((nY > 0) && !pxChecked[(nY - 1) * 19 + i])                 RemoveStones(i, nY - 1, xStone, pxChecked);             if ((nY < 19 - 1) && !pxChecked[(nY + 1) * 19 + i])                 RemoveStones(i, nY + 1, xStone, pxChecked);         }     } } void CBadukDoc::RemoveDeadStones(int nX, int nY, BYTE xStone) {     LPBYTE pxChecked = new BYTE[19 * 19];     ZeroMemory(pxChecked, 19 * 19);     RemoveStones(nX, nY, xStone, pxChecked);     delete [] pxChecked; } void CBadukDoc::CheckDeadStone(int nX, int nY, BYTE xStone) {     BYTE xStoneToCheck;     if (xStone == 1)         xStoneToCheck = 2;     else if (xStone == 2)         xStoneToCheck = 1;     else         return;     if (nX > 0)        // left     {         if (IsDeadStone(nX - 1, nY, xStoneToCheck))             RemoveDeadStones(nX - 1, nY, xStoneToCheck);     }     if (nX < 18)    // right     {         if (IsDeadStone(nX + 1, nY, xStoneToCheck))             RemoveDeadStones(nX + 1, nY, xStoneToCheck);     }     if (nY > 0)        // up     {         if (IsDeadStone(nX, nY - 1, xStoneToCheck))             RemoveDeadStones(nX, nY - 1, xStoneToCheck);     }     if (nY < 18)        // up     {         if (IsDeadStone(nX, nY + 1, xStoneToCheck))             RemoveDeadStones(nX, nY + 1, xStoneToCheck);     } }

[=]  http://www.devpia.com/Search/MAEULResult.aspx?page=3&keyw=%b9%d9%b5%cf%bc%d2%bd%ba