PKU 1904. King's Quest. [판정:WA]

ㅋㅋㅋ 젠장

알고리즘이 정리되지 않는 상태에서 그냥 막코딩했더니 이모양이군요 -_-;

solving process에 올려놓은 케이스에 대해서는 잘 나옵니다만

아마 어딘가 틀렸으니 wa겠지요? =_=

#include <iostream> #include <list> using namespace std; enum purity { CLEAN, DIRTY }; class Vertex { public: int odeg; int *dest; purity status; Vertex() { odeg = 0; dest = NULL; status = CLEAN; } }; list<int> *ls; list<int>::iterator iter; void permutation( Vertex *pv, int n, int depth ); int main() { Vertex *vs; int princes, likes; int i, j, temp; scanf("%d", &princes); vs = new Vertex[1+princes]; for( i = 1; i <= princes; i++ ) { scanf("%d", &likes); vs[i].odeg = likes; vs[i].dest = new int[1+likes]; //vs[i].status = CLEAN; omit-able for( j = 1; j <= likes; j++ ) { scanf("%d", &vs[i].dest[j]); } } for( i = 1; i <= princes; i++ ) { scanf("%d", &temp); } ls = new list<int>[1+princes]; permutation( vs, 1, princes ); // ascendant sorting for( i = 1; i <= princes; i++ ) { ls[i].sort(); } // printing for( i = 1; i <= princes; i++ ) { printf("%d", ls[i].size()); for( iter = ls[i].begin(); iter != ls[i].end(); iter++ ) { printf(" %d", *iter); } printf("\n"); } return 0; } void permutation( Vertex *pv, int n, int depth ) { /* n: vertex number * now: selected edge number * des: destination vertex number */ int now = 1; int des; int maxdeg, escape; int insert = 0; maxdeg = pv[n].odeg; while( now <= maxdeg ) { des = pv[n].dest[now]; escape = 0; insert = 0; while( pv[des].status == DIRTY ) { now++; if( now > maxdeg ) { escape = 1; break; } des = pv[n].dest[now]; } if( escape ) return; // return fail else { pv[des].status = DIRTY; for( iter = ls[n].begin(); iter != ls[n].end(); iter++ ) { if( *iter == des ) break; } if( iter == ls[n].end() ) { insert = 1; ls[n].push_back(des); } if( depth == 1 ) { pv[des].status = CLEAN; return; // return success } else { permutation( pv, n+1, depth-1 ); } } pv[des].status = CLEAN; now++; } return; // return success }

DFS나 BFS와는 관계없습니다만, 컨셉은 유향그래프입니다

코드 윗부분에 나온 열거형 자료형(맞나?)은

DFS나 BFS에서 쓰는 unexplored, visited, back(cross) edge의 의미를 가지고 있습니다

설명은 패스하겠습니다;

대충 어떤 알고리즘인지는 머리에 있지만 그것을 설명할 말이 떠오르지 않는 관계로 -_-;;

아 그리고,

방학중에 열심히 하던 게임을 끊었더니 급재부팅은 줄어든 듯 합니다

봐서 컴퓨터 상태가 좋으면 이번주 목요일엔 포스팅이 가능할지도 모르겠습니다