PKU 1979. Red and Black. [판정:AC]

발견 하나, 제목을 줄이면 R&B가 됩니다 :D

#include <stdio.h> #include <stdlib.h> int getRow( int position ); int getCol( int position ); void search( char *fld, char *brd, int position ); void RedNBlack( char *fld, int ara, int origin ); int row; int column; void main() { char *field; while(1) { scanf("%d %d", &column, &row); if( row == 0 && column == 0 ) break; else if( row > 0 && column > 0 ) { int area = row * column; int i; char temp; int starting; field = ( char* )calloc( area, sizeof( char ) ); for( i = 0; i < area; ) { temp = getchar(); if( temp == '@' ) { starting = i; } if( temp != '\n' ) { field[i] = temp; i++; } } RedNBlack( field, area, starting ); free( field ); } } } int getRow( int position ) { return ( position / column ); } int getCol( int position ) { return ( position % column ); } void search( char *fld, char *brd, int position ) { int target; // Up if( getRow( position ) > 0 && fld[ position-column ] != '#' ) { target = position - column; if( brd[ target ] == 0 ) { brd[ target ] = 1; search( fld, brd, target ); } } // Left if( getCol( position ) > 0 && fld[ position-1 ] != '#' ) { target = position - 1; if( brd[ target ] == 0 ) { brd[ target ] = 1; search( fld, brd, target ); } } // Down if( getRow( position ) < row-1 && fld[ position+column ] != '#' ) { target = position + column; if( brd[ target ] == 0 ) { brd[ target ] = 1; search( fld, brd, target ); } } // Right if( getCol( position ) < column-1 && fld[ position+1 ] != '#' ) { target = position + 1; if( brd[ target ] == 0 ) { brd[ target ] = 1; search( fld, brd, target ); } } } void RedNBlack( char *fld, int ara, int origin ) { char *count = ( char* )calloc( ara, sizeof( char ) ); int i; int movable = 0; count[origin] = 1; search( fld, count, origin ); for( i = 0; i < ara; i++ ) { movable += count[i]; } printf("%d\n", movable); free( count ); }

연속해서 두 문제를 풀려니 머리가 잘 안돌아가는 느낌이네요//

처음에 받은 CE는

void main()을 썼다고 -_- 나온 결과이고,

(습관상 void main()을 쓰는데, C++로 제출하면 int main()만 허용하더군요)

두번째 받은 WA는

이 문제를 해결할 당시(무려 20일 전이군요) 문제의 내용이 '미로찾기'와 유사한 것 같아서

'행과 열의 순서쌍'을 나타내는 class를 하나 만들고, 따로 스택도 구현해서

시작점 '@'에서 도달할 수 있는 모든 위치에 대해 스택에 저장해두고 마지막에 top+1 을 출력하는 형태로 구현했습니다

-만,

sample input/output에 대해서 답이 나오길래 제출했더니 WA가 뜨는 것으로 보아 뭔가 알고리즘상의 문제가 있었나봅니다

아까 Quicksum을 풀고 이걸 다시 봤더니 뭔가 소스가 복잡해서 보기 불편하길래

다 지우고 처음부터 만들었습니다

'상-좌-하-우'의 우선순위로 탐색하며,

'#'가 아니면서 탐색되지 않은 부분이 발견되면 그 부분의 값을 1로 바꾸어주고, 다시 '상-좌-하-우'의 우선순위로 탐색합니다

추신: to 지군,

- 이제 내가 이거 풀었으니 문제 번역할 명분이 생겼지? :D