Google code jam 2010 Round A : Problem A

Problem : http://code.google.com/codejam/contest/dashboard?c=544101#s=p0&a=0

문제 접근

Rotation 후 중력작용이라고 했는데 결국 둘을 종합해서 Gravity방향을 파악해서 땡겨주면 된다는 점을 아는게 핵심이면 핵심이겠다. ( 이걸 몰라도 답은 구하겠지만, 소스 TLE나올 우려가 있다.) 나름 TLE 염려하면서 코딩했는데도 Large Set 컴파일하니까 0.5초정도 걸리더라..

천천히 모듈별로 짜서 하루 걸렸다. 문제에서 clockwise의 단어를 몰라서 그냥 그러려니 하고 넘어갔다가 나중에 90도 방향으로 1번 돌릴 수 있다고 해서... 나는 왼쪽 오른쪽 전부 코딩했다..;; 그리고 처음 상태에서 판별 + 회전한 상태에서 모두 판별 해서 이상하게 종합된 결과를 내서 Incorrect를 계속 받았다.. -_-;;  (역시 영어가 엄청 중요하다 ㅠㅠ - 해석이 어렵다가 이제는 아예 잘못읽어서 산으로 가다니...;;)

Rotation도 다 짜고 가만생각하니까 필요가 없었고... Gravity방향만 조절해주면 되었다..
여러모로 삽질을 많이 했던 문제.
디버깅할때 winCondition Size를 1줄이지 않은것때문에 2시간정도 찾다가 완전 의욕 잃고 게임좀하다가 다시 예제 하나하나 살펴보다가 이상한 곳을 발견해서 추적해 찾았다 -_ㅠ...

역시 WA가 뜰때는 완전 포기한 상태에서 처음부터 차근따라가는게 좋은 수다..;;

//right gravity
  for(int i=0; i<mapsize; i++)
  {
   int cnt=0;
   for(string::iterator iter=right[i].begin(); iter!=right[i].end(); )
   {
    if(*iter == '.') 
    {
     iter = right[i].erase(iter);
     cnt++;
    }
    else iter++;
   }
   if(cnt==mapsize) continue;
   else
   {
    for(int j=0; j<cnt; j++)
     right[i].insert(0,".");
   }
  }
  //checking Winner
  result = checking(right, winCondition, mapsize, &Bwin, &Rwin);

모듈별로 나눠서 코딩해서 그런지 코드가 나름 짧게 짰다. 하지만 그래도 130라인 ;;
8방향 삽질을 줄이고자 노력했으나,  쩝...;; 비슷한 라인이 뭉탱이로 있는곳이 군데군데 보인다 ㅠ
int를 리턴하는데, 0 : Neither, 1 : Blue, 2 : Red, 3 : Both 를 의미한다.

int checking(string* map, int win, int size, bool* Bwin, bool* Rwin)
{
 const char** tmp = new const char*[size];
 for(int i=0; i<size; i++)
 {
  tmp[i] = map[i].c_str();
 }
 for(int i=0; i<size; i++)
 {
  for(int j=0; j<size; j++)
  {
   if(tmp[i][j]=='B'&&!(*Bwin) || tmp[i][j]=='R'&&!(*Rwin))
   {
    bool flag=false;
    // 8방향에 대한 test 호출
    if(direction8(tmp, i, j, -1, -1, win-1, size)){flag=true;} //좌상
    else if(direction8(tmp, i, j, -1,  0, win-1, size)){flag=true;} //상
    else if(direction8(tmp, i, j, -1,  1, win-1, size)){flag=true;} //우상
    else if(direction8(tmp, i, j,  0,  1, win-1, size)){flag=true;} //우
    else if(direction8(tmp, i, j,  1,  1, win-1, size)){flag=true;} //우하
    else if(direction8(tmp, i, j,  1,  0, win-1, size)){flag=true;} //하
    else if(direction8(tmp, i, j,  1, -1, win-1, size)){flag=true;} //좌하
    else if(direction8(tmp, i, j,  0, -1, win-1, size)){flag=true;} //좌
    if(flag && tmp[i][j]=='B') *Bwin=true;
    else if(flag && tmp[i][j]=='R') *Rwin=true;
   }
  }
 }
 if(*Bwin && *Rwin) return 3;
 else if(*Rwin) return 2;
 else if(*Bwin) return 1;
 else return 0;
}

자질구레한 if문장이 엄청많은 이유는 8방향에 대한 제한 조건이 각각 달라서이다 ㅠ...
(처음에 엉뚱한 생각으로 통합했다가 디버깅으로 고친 문장..;;)
if문장은 Time Complexity에 큰 영향을 안주기에 더덕더덕 붙여서 썼다.

bool direction8(const char** map, int x, int y, int dir1, int dir2, int win, int size)
{
 bool winflag = true;
 //해당 direction 방향으로 진행할때 map을 벗어나는 경우 false 처리
 if( dir1==-1 && dir2==-1 ) //좌상
 { if(x+dir1*win<0 || y+dir2*win<0) return false;}
 else if(dir1==-1 && dir2==0) //상
 { if(x+dir1*win<0) return false;}
 else if(dir1==-1 && dir2==1) //우상
 { if(x+dir1*win<0 || y+dir2*win>=size) return false;}
 else if(dir1==0  && dir2==1) //우
 { if(y+dir2*win>=size) return false;}
 else if(dir1==1  && dir2==1) //우하
 { if(x+dir1*win>=size || y+dir2*win>=size) return false;}
 else if(dir1==1  && dir2==0) //하
 { if(x+dir1*win>=size) return false;}
 else if(dir1==1  && dir2==-1) //좌하
 { if(y+dir2*win<0 || x+dir1*win>=size) return false;}
 else if(dir1==0  && dir2==-1) //좌
 { if(y+dir2*win<0) return false;}

 for(int i=1; i<=win; i++)
 {
  if(map[x][y] != map[x+dir1*i][y+dir2*i])
   winflag =false;
 }
 return winflag;
}