[4일차][그래프] 최소거리

- 문제 설명

그래프에서 0번노드에서 시작해 n번노드로 도착하는 최소거리 구하라

- 입력

1 // 테스트 케이스

2 3 // 2번노드가 마지막 노드, 엣지 3개

0 1 // 0->1 가능

0 2 // 0->2 가능

1 2 // 1->2 가능

- 출력

#1 1 // 테스트케이스, 0->2로 한번에 갈 수 있기때문에 1

- 입력 예시

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 1
#2 2
#3 2

- 코드

#include "stdio.h"

void findShortestPath(int startNode);

int queue[21];

int front = -1;

int rear = -1;

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

int visit[21];

int node;

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

    int T;

    scanf("%d", &T);

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

    {

        front = -1;

        rear = -1;

        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;

        }

        findShortestPath(0);

        printf("#%d %d\n",tc,visit[node] - visit[0]);

    }

    return 0;

}

void findShortestPath(int startNode)

{

    // 초기화

    queue[++rear] = startNode; // enqueue

    visit[startNode] = 1; // 처음 거리를 1로 초기화

    while ( front != rear)

    {

        startNode = queue[++front]; // dequeue

        //        printf("%d ", n);

        for(int i=1;i<= node; i++)

        {

            if(graph[startNode][i] == 1 && visit[i] == 0) // 인접하고 방문하지 않은 경우

            {

                queue[++rear] = i; // enqueue

                visit[i] = visit[startNode]+1; // 방문거리는 이전 거리보다 하나 더 크게

            }

        }

    }

}