[Inflearn] 그래프 최단거리(BFS : Queue 사용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 1번 정점에서 각 정점으로 가는 최소 이동 간선 수

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

우선 인접리스트를 만들어보자.

BFS에 필요한 Queue 와 최소 간선 수를 구하기 위해 dis[] 배열이 필요하다.

Queue

dst[]

1	2	3	4	5	6

먼저 1번 정점에서 출발하므로 

Queue 에 1을 push 해준다.

1은 출발점이니까 dst 는 0이다.

Queue

1

dst[]

1	2	3	4	5	6
0

Queue 에서 1을 빼내고 정점 1에서 갈 수 있는 정점을 탐색한다.

정점 1에서 갈 수 있는 정점은 3번, 4번이다.

먼저 가까운 3번 정점으로 가기 위해 3번을 Queue 에 push

1번부터 3번까지 가는데 간선 수는 1개 이므로 dst[3] 에 1을 체크해준다.

dst[3] = dst[0] + 1

Queue

3

dst[]

1	2	3	4	5	6
0		1

또, 1번 정점에서 4번으로 갈 수 있다.

마찬가지로 1번에서 4번으로 가는데 하나의 간선을 사용한다.

dst[4] = dst[0] + 1

Queue

3   4

dst[]

1	2	3	4	5	6
0		1	1

이제 더이상 1번에서 갈수 있는 정점은 없으므로

Queue 에서 3을 빼내고 3번에서 갈 수 있는 정점을 탐색한다.

4번밖에 없다.

하지만 4번은 이미 dst에 체크되어있으므로 pass 한다.

(3번은 1번을 거쳐와서 4번으로 가는데 두 개의 간선이 사용되지만 이미 4번 정점은 1번으로부터 

한 개의 간선으로 왔기때문에 최소 간선 수로 이미 체크된 상태이다.)

Queue

4

dst[]

1	2	3	4	5	6
0		1	1

이제 Queue 에서 4를 빼내고 4번 정점에서 갈수 있는 정점을 탐색한다.

5번, 6번이 있다.

dst[5] = dst[4] + 1

dst[6] = dst[4] + 1

Queue

5   6

dst[]

1	2	3	4	5	6
0		1	1	2	2

계속 Queue 에서 5번을 빼낸다.

5번에서 갈 수 있는 정점은 없다. 패스

Queue

6

dst[]

1	2	3	4	5	6
0		1	1	2	2

Queue 에서 6번을 빼낸다.

6번에서 갈 수 있는 정점은 2번이다. 

Queue 에 push!

dst[2] = dst[6] + 1

Queue

2

dst[]

1	2	3	4	5	6
0	3	1	1	2	2

다음으로 Queue 에서 2를 빼내고 정점 2에서 갈 수 있는 정점을 탐색한다.

Queue 는 비어있는 상태가 되었으므로 종료한다.

재귀함수보다 접근은 더 쉬운 것 같다.

BFS도 시뮬레이션해보면서 빨리 익숙해져야지!

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int dst[21];
vector<int> map[21];
queue<int> q;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, m, a, b, i, x;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
 
        map[a].push_back(b);
    }
 
    q.push(1);
 
    while (!q.empty())
    {
        x = q.front();
        q.pop();
 
        for (i = 0; i < map[x].size(); i++)
        {
            if (dst[map[x][i]] == 0)
            {
                q.push(map[x][i]);
                dst[map[x][i]] = dst[x] + 1;
            }
        }
    }
 
    for (i = 2; i <= n; i++)
        printf("%d : %d\n", i, dst[i]);
 
    return 0;
}

line 19~24) 인접리스트를 생성한다.

line 26) 1번 정점부터 시작하므로 먼저 queue 에 1을 넣어준다.

이제 시작이다.

line 28~41) queue 가 비어있을 때까지 탐색을 반복한다.

line 30) queue 제일 앞에 있는 원소를 참조

line 31) queue 제일 앞에 있는 원소를 참조하였으므로 빼내준다.

line 33) 해당 원소와 연결과 정점들을 탐색

line 35) 탐색한 정점을 방문한 기록이 없다면 queue 에 정점 번호를 넣어주고,

          dst 에 해당 정점까지의 거리를 저장

이 과정이 queue 가 비어있을 때까지 반복된다. 

자세한 과정은 풀이를 참고해보면 될 것 같다.

#. Other code

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
int ch[30], dis[30];
 
int main(){
    int n, m, a, b, x, i;
    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;
}

#. Result

  - Input --------------------------------------------------------

6 9 

1 3 

1 4 

2 1 

2 5 

3 4 

4 5 

4 6 

6 2 

6 5

------------------------------------------------------------------

  - Output --------------------------------------------------------

2 : 3 

3 : 1 

4 : 1 

5 : 2 

6 : 2

------------------------------------------------------------------