재귀호출과 완전탐색

문제 1

0번부터 차례대로 번호 배겨진 n개의 원소 중 4개를 고르는 모든 경우

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

//n:전체 원소 수
//picked :지금까지 고른 원소들의 번호
//toPick : 더 고를 원소의 수
// 일때 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다

void pick(int n, vector<int>& picked, int toPick){
	//기저 사례 : 더 고를 원소가 없을때 고른 원소들을 출력한다.
    if(toPick==0){printPicked(picked); return;}
    //고를 수 있는 가장 작은 번호를 계산한다.
    int smallest = picked.empty() ? 0  : picked.back() +1;
    //이 단계에서 원소 하나를 고른다.
    for(int next = smallest; next < n; ++next){
    	picked.push_back(next);
        pick(n,picked,toPick-1);
        picked.pop_back();
    }
}

문제 2

5*5 보글 게임 알파벳단어 찾기

보글 게임판에서 단어를 찾는 재귀호출 알고리즘

const int dx[8]= {-1,-1,-1,1,1,1,0,0};
const int dy[8]= {-1,0,1,-1,0,1,-1,1};

//5x5 보글 게임판의 해당 위치에서 주어진 단어가 시작하는지를 반환
bool hasWord(int y, iny x, const string& word){
	
    //기저사례 1 : 시작위치가 범위 밖이면 무조건 실패
    if(!inRange(y,x)) return false;
    
    //기저 사례 2 : 첫글자가 일치하지 않으면 실패
    if(board[y][x] != word[0]) return false;
    
    //기저 사례 3: 단어 길이가 1이면 성공
    if(word.size()==1) return true;
    
    //인접한 8칸을 검사
    for(int direction =0; direction < 8 ; ++direction){
    	int nextY = y+dy[direction], nextX = x+dx[direction];
        //다음 칸이 범위 안에 있는지 첫글자는 일치하는지 확인할 필요 없음
        if(hasWord(nextY,nextX,word.substr(1)))
        	return true;
    }
    return false;
}

이 알고리즘은 단어의 길이가 짧은 경우에만 완전탐색으로 해결할 수 있다.
단어가 긴 경우는 후에 다시 다루도록 하겠다.

문제 3

소풍 문제

• 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질때 학생들을 짝 지을수 있는 방법의 수를 계산하시오.

소풍 문제를 해결하는 재귀 호출 코드

int n;
bool areFriends[10][10];
//tackenp[i]= i 번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
	//남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
    int firstFree = -1;
    for(int i=0; i< n;i++){
    	if(!taken[i]){
        	firstFree = i;
            break;
        }
    }
    //기저 사례 : 모든 학생이 짝을 찾았으면 한가지 방법을 찾았으니 종료
    if(firstFree == -1) return 1;
    int ret =0;
    //이학생과 짝지을 학생을 결정한다.
    for(int pairWith = firstFree+1; pairWith < n; ++pairWith){
    	if(!taken[pairWith] && areFriends[fisrtFree][pairWith]{
        	taken[firstFree] = taken[pairWith] = true;
            ret += countPairings(taken);
            taken[firstFree] = taken[pairWith] = false;
        }
        
    }
    return ret;
}

/*
(0,1)과 (1,0)은 같다. 같은 방법을 중복으로 세지 않도록 주의하자.
-> 각 단계에서 남아있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 한다.
-> 가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일수밖에 없기에 방법이 중복될일이 없다.
*/

**프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만) 참고하여 공부 기록하였습니다.