[4일차][그래프] n으로 도착하는 경로 개수

- 문제 설명

0~n까지 노드로 구성된 그래프

도착노드로 가는 경로의 갯수 구하기

- 입력

1 // 테스트 케이스

2 3 // 노드 갯수, 그래프 갯수

0 1 // 0->1번 갈 수 있음

0 2 // 0 -> 2번 갈 수 있음

1 2 // 1 -> 2번 갈 수 있음

- 출력

#1 2 // 테스트 케이스, 경로 갯수

- 입력 예시

3
2 3
0 1
0 2
1 2
4 7
0 1
0 2
0 3
1 4
2 3
2 4
3 4
7 20
0 1
0 2
0 5
1 2
1 4
1 5
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 6
3 7
4 5
4 6
4 7
5 7
6 7

- 출력 예시

#1 2
#2 4
#3 28

- 코드

int graph[21][21]; // 그래프

int visit[21];

void findNumberOfWay(int nodeNum, int dstNum);

int node;

int numOfVisitWay;

int main(int argc, const char * argv[]) {

    int T;

    freopen("/Users/wjhur/Desktop/ctest/ctest/Text.txt", "r", stdin);

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        int edge;

        scanf("%d %d",&node, &edge);

        

        for(int i=0;i <node+1;i++) // 그래프 초기화

        {

            for(int j=0;j < node+1;j++)

            {

                graph[i][j] = 0;

            }

        }

        

        for(int i=0; i < edge; i++) // 엣지 갯수만큼

        {

            int n1,n2;

            scanf("%d %d",&n1,&n2);

            graph[n1][n2] = 1;

        }

        numOfVisitWay =0;

        findNumberOfWay(0,node);

        printf("#%d %d\n",tc,numOfVisitWay);

    }

    return 0;

}

void findNumberOfWay(int nodeNum, int dstNum)

{

    if(nodeNum == dstNum) // 도착하면

    {

        numOfVisitWay++; // 경로 갯수 증가

    }

    else

    {

        visit[nodeNum] = 1; // 현재 노드는 방문했다고 표시

        for(int i=1;i<=node;i++) //  노드 갯수만큼 돌면서

        {

            if(visit[i] == 0 && graph[nodeNum][i] == 1) // 현재 방문 안한 노드고 갈 수 있으면

            {

                findNumberOfWay(i,dstNum); // 다음 노드로

            }

        }

        visit[nodeNum] = 0; // 여기 오는 경우 끝까지 다 간경우이므로 현재 노드 방문표시 지우기

    }

}