경로의 수(C++)

출발점이(0.0)이고 도착점이 (n-1, n-1)라고 할때, 출발점에서 도착점까지 가는 길의 수를 구하는 프로그렘을 만들어 보자. 1은 지나갈 수 있는 길이고 0은 갈 수 없는 길이다. 입력은 N x N크기의 1과 0으로 이루어진 2차원 수열로 이루어지고 경로의 수를 구해 출력하면 된다.(N은 10이하이다.



DFS를 이용해 모든 경우를 순서대로 검색하고 카운트한 다음 출력하면 된다.



#include <iostream>
#include <windows.h>

using namespace std;

int a[10][10];
int n,c;//전역변수는 자동으로 0으로 초기화 된다.
void move(int y,int x){
    
     if(x==n-1&y==n-1){
                       c++;
                       return;
                       }
    
     a[y][x]=0;//경로를 되돌아 오는 것을 막기위해 0으로 바꾼다.
     if(x>0&&a[y][x-1]==1)move(y,x-1);
     if(y>0&&a[y-1][x]==1)move(y-1,x);
     if(x<n-1&&a[y][x+1]==1)move(y,x+1);
     if(y<n-1&&a[y+1][x]==1)move(y+1,x);
    
     return;
}
int main(){
   
    int i,j;
    cin>>n;
   
    for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>a[i][j];
   
    move(0,0);
    cout<<c<<endl;
   
    system("PAUSE");
   
    return 0;
}

출력 결과
5
1 1 1 0 0
0 0 1 1 1
0 1 1 0 1
1 1 0 0 1
1 1 1 1 1
2
Press any key to continue . . .

그러나 이러한 방법은 왔던 길을 0으로 초기화 하기 때문에 중간에 다시 합류하는 지점이 생길때 이미 검색이 완료된 길이면 없는 길이 되어 버려 경로를 검색하지 못한다.

따라서 궁극적으로 도착지점에 직접적으로 연결된 길이 몇개인지 새는 것과 다를 바가 없으며, 그러므로 출력값은 2를 넘을 수 없게 된다.