70. 그래프 최단거리 [BFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

6 9

1 3

1 4

2 1 

2 5

3 4

4 5

4 6

6 2

6 5

 

출력예제 1

2 : 3

3 : 1

4 : 1

5 : 2

6 : 2

 

풀이 

- 1번 정점부터 n번 정점까지 최소로 갈 수 있는 횟수를 찾는다(2~n번까지 출력)

- distance 배열을 사용하는것이 핵심

- 1번에서 출발하기 때문에 2번부터 구하면 된다. 1번은 미리 큐에 넣어놓고 ch[1]=1로 만든다

- x변수는 항상 큐의 front값을 가지고, x에 값을 담은 후에 큐에서 빠진다.

- x에서 한번에 갈 수 있는 연결 정점을 탐색한다 (연결리스트 형식이기 때문에 i는 0~map[x].size()까지 반복)

- 만약 ch[map[x][i]]==0이면 해당 체크를 1로 만들고 큐에 담아 준다.

- 해당 정점(map[x][i]의 값)의 dis 값을 x번째값(이미 거쳐온 정점의 거리값)에 1 더한 값으로 설정한다. => dis[x]+1

- 다음 사이클이 돌면 Q.front값은 처음 정점에서 이동한 정점값이 되고, 해당 정점에서 한번에 갈 수 있는 정점을 찾는 동일한 형식으로 진행된다.

 

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int ch[30], dis[30];

//70. 그래프 최단거리(BFS)
int main(){
    //1번 정점에서 각 정점으로 가는 최소 간선수 2번 정점부터(방향그래프)
    int n, m, i, a, b, x; //n: 정점 수, m: 간선 수
    vector<int> map[30];
    queue<int> Q;
    scanf("%d %d", &n, &m);
    for(i= 1; i<=m; i++){
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
    }
    Q.push(1);
    ch[1]=1;
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        for(i=0;i<map[x].size();i++){
            if(ch[map[x][i]]==0){
                ch[map[x][i]]=1;
                Q.push(map[x][i]);
                dis[map[x][i]]=dis[x]+1;
            }
        }
    }
    for(i=2;i<=n;i++){
        printf("%d : %d\n", i, dis[i]);
    }
    return 0;
}