2. BFS Referenct Code - 노드 유형, 백준 1260, 2606, 2644

 

Q. BFS 모든 경로의 거리를 구하시오

 

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#define MAX_SIZE 101
using namespace std;

int ch[MAX_SIZE], dis[MAX_SIZE];

int main(void) {
    int n, m, a, b, x;
    
    vector<int> map[MAX_SIZE];
    queue<int> Q;
    scanf("%d%d", &n, &m);  
    
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
    
    Q.push(1);
    ch[1] = 1;
    
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        for(int 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(int i=2;i<=n;i++){
        printf("%d : %d\n", i, dis[i]);
    }
    
    return 0;
}

 

 

- BFS는 큐를 사용하여 구현한다.

 

< 원리 >

1. 첫 번째 정점과 연결되어 있는 모든 정점을 확인

2. 해당 정점을 이전에 방문하지 않았을 경우 큐에 넣는다.

3. 1, 2번을 모두 완료한 후, 큐에서 그 다음 정점을 꺼내어 똑같은 과정을 반복한다.

 

 

 

 

 

 

응용문제1) 백준 1260 중 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int ch[30], dis[30];        // ch는 방문했는지 안했는지

int main(void) {
    int n, m, a, b, x, start;
    
    vector<int> map[30];
    queue<int> Q;
    scanf("%d%d%d", &n, &m, &start);
    
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
    
    // 작은 수부터 조건이 있으니까 정렬해주기
    for(int i=1; i<=n; i++){
        sort(map[i].begin(), map[i].end());
    }
    
    Q.push(start);
    ch[start] = 1;
    
    while(!Q.empty()){
        printf("%d ", Q.front());
        x = Q.front();
        Q.pop();
        
        for(int i=0; i<map[x].size(); i++){
            
            if(ch[map[x][i]] == 0){
                ch[map[x][i]] = 1;
                Q.push(map[x][i]);
            }
        }
    }
    return 0;
}

 

 

 

 

- 작은 수부터 먼저 탐색하라는 문제의 조건이 있으므로 정렬을 해준다.

- 1 대신 start 값을 받아서 시작 정점을 정해준다.

- BFS를 수행한다.

 

 

 

 

응용문제2) 백준 2606 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int ch[101];

int main(void) {
    int n, m, a, b, x, cnt = 0;
    
    vector<int> map[101];
    queue<int> Q;
    scanf("%d%d", &n, &m);      // 두 줄에 나눠서 입력해도 가능한가? 가능!
    
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
    
    Q.push(1);
    ch[1] = 1;
    
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        for(int i=0; i<map[x].size(); i++){
            if(ch[map[x][i]] == 0){
                ch[map[x][i]] = 1;
                Q.push(map[x][i]);
                cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    
    return 0;
}

 

 

- 거리 대신 방문횟수를 구해야 하므로 cnt 변수를 넣어주고, 방문할 때마다 하나씩 증가하도록 했다.

- 배열 ch와 벡터배열 map 의 크기를 문제에 맞추어 101로 증가시켰다.

 

 

 

 

 

 

응용문제3) 백준 2644 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int ch[101], dis[101];
int s, f;

int main(void) {
    int n, m, a, b, x;
    
    vector<int> map[101];
    queue<int> Q;
    scanf("%d", &n);
    scanf("%d%d", &s, &f);
    scanf("%d", &m);
    
    
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
    
    Q.push(s);
    ch[s] = 1;
    
    while(!Q.empty()){
        x=Q.front();
        if(x == f)
            break;
        Q.pop();
        for(int 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;
            }
        }
    }
    
    if(dis[f] == 0)
        dis[f] = -1;
    printf("%d\n", dis[f]);
    
    return 0;
}

 

- 배열 ch, dis와 벡터배열 map 의 크기를 문제에 맞추어 101로 증가시켰다.

- 시작노드와 마지막노드를 받아서 시작 노드부터 출발을 하였고, 마지막노드가 나왔을 때 break; 해 주었다.

- 관계가 아예 없다면(dis[f] == 0) -1을 출력하도록 하였다.