2014년 7월 22일 화요일

1012 - 유기농 배추

DFS나 BFS와 같은 전탐색으로 문제를 해결할 수 있다.
필자는 DFS를 사용했는데, int dirt[4]={-1,0,1,0}; 과 같이 선언하고

08int DFS(int y, int x, int H /*최대 높이*/, int W /*최대 너비*/)
09{
10    if( /* Base Case; 기저 케이스 */ ) return 0;
15    for(int i=0; i < 4; ++i)
16        DFS( y+dirt[(i+3)%4], x+dirt[i], H, W );
17    return 1;
18}

위와 같이 [상(-1,0), 우(0,-1), 하(+1,0), 좌(0,+1) ]의 조합을 배열 하나로 사용했다.

여기서 DFS가 return 1; 을 했다. 이건 한 덩어리(구간)의 출발점만 리턴될 것이다.
왜냐하면 기저 케이스에서 "방문한 노드"는 return 0; 으로  걸러질 것이기 때문이다.
댓글 쓰기

게시글 목록