PKU 1422. Air Raid. [판정:RE]

RE받은거라서 안올리려고 했는데 ( 만약 RE가 아니었다면 WA였겠지만 )

그냥

블로그 돌아가는 느낌은 내야되니까 올려보아요 :)

알고리즘은 "그래프 자료구조"를 이용했다고 생각하시면 됩니다

실제로 그래프를 구현하지는 않았지만 -_-;

이전 솔루션들과 비교했을 때

변수명이 좀 낯설게 보이실 수 있습니다만

최근에 API 공부할 때 보니, API 책에서 변수명 앞에 알파벳을 붙여주는 것이 좋다고 해서

( 이미 전에도 컴공 조교들한테 들었던 얘기인데 귀찮아서 안했는데, API 책의 예제는 싸그리 그런 형식이라서 어쩔 수 없이 '-' )

나름 그런 형식을 지켜본 것입니다 :)

#include <iostream> using namespace std; enum View { NO, YES }; class Street { public: View eVI; int *aEndPoints; int iNowEP; int iMaxEP; Street() { int iiFor; eVI = NO; iNowEP = 0; iMaxEP = 4; aEndPoints = new int[iMaxEP +1]; for( iiFor = 1; iiFor <= iMaxEP; iiFor++ ) { aEndPoints[iiFor] = 0; } } void reNew() { int *aTemp = new int[iMaxEP *2 +1]; int iiFor; for( iiFor = 1; iiFor <= iMaxEP; iiFor++ ) { aTemp[iiFor] = aEndPoints[iiFor]; } iMaxEP *= 2; for( ; iiFor <= iMaxEP; iiFor++ ) { aTemp[iiFor] = 0; } swap( aTemp, aEndPoints ); delete[] aTemp; } void inputEP( int iEndPoint ) { if( iNowEP == iMaxEP ) { reNew(); } aEndPoints[iNowEP +1] = iEndPoint; iNowEP++; } }; class Town { public: int iNumOfINTRSCTN; int iNumOfStreets; Street *saST; Town() { saST = NULL; } void inputSE( int *lps, int *lpe ) { scanf( "%d %d", lps, lpe ); saST[*lps].inputEP( *lpe ); } void clear() { int iiFor; for( iiFor = 1; iiFor <= iNumOfINTRSCTN; iiFor++ ) { delete[] saST[iiFor].aEndPoints; } delete[] saST; } }; void AirRaid( Town &sTO ); int main() { int iNumOfTowns; Town sTO; int iTemp; int iiFor; int iStart, iEnd; scanf( "%d", &iNumOfTowns ); while( iNumOfTowns > 0 ) { scanf( "%d", &sTO.iNumOfINTRSCTN ); scanf( "%d", &sTO.iNumOfStreets ); iTemp = sTO.iNumOfStreets; if( sTO.saST == NULL ) { sTO.saST = new Street[sTO.iNumOfINTRSCTN +1]; } else { sTO.clear(); sTO.saST = new Street[sTO.iNumOfINTRSCTN +1]; } for( iiFor = 1; iiFor <= iTemp; iiFor++ ) { sTO.inputSE( &iStart, &iEnd ); } AirRaid( sTO ); iNumOfTowns--; } return 0; } void AirRaid( Town &sTO ) { int iCount = 0; int iiFor; bool bIsExit; int iTemp, iTemp2; while( 1 ) { bIsExit = true; iTemp = 0; for( iiFor = 1; iiFor <= sTO.iNumOfINTRSCTN; iiFor++ ) { if( sTO.saST[iiFor].iNowEP != 0 ) { if( bIsExit == true ) { bIsExit = false; } if( iTemp == 0 ) { iTemp = iiFor; } } } if( bIsExit == true ) { break; } while( 1 ) { sTO.saST[iTemp].eVI = YES; if( sTO.saST[iTemp].iNowEP == 0 ) { break; } for( iiFor = 1; sTO.saST[iTemp].aEndPoints[iiFor] == 0; iiFor++ ) { ; } iTemp2 = sTO.saST[iTemp].aEndPoints[iiFor]; sTO.saST[iTemp].aEndPoints[iiFor] = 0; sTO.saST[iTemp].iNowEP--; iTemp = iTemp2; } iCount++; bIsExit = true; for( iiFor = 1; iiFor <= sTO.iNumOfINTRSCTN; iiFor++ ) { if( sTO.saST[iiFor].eVI == NO ) { bIsExit = false; } } if( bIsExit == true ) { break; } } printf( "%d\n", iCount ); }