가전제품 이것저것 이야기

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

#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

#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

#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을 출력하도록 하였다.

Q. DFS 로 갈 수 있는 모든 경로의 수는?

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

int map[30][30], ch[30], cnt = 0;
int n, m;

void DFS(int v){            // v -> 정점 번호
    if(v == n) {
        cnt++;
    }
    else {
        for(int i=1; i<=n; i++){
            if(map[v][i] == 1 && ch[i] == 0){
                ch[i] = 1;                          // 한 번 길 갈 때, 똑같은 곳을 또 방문하지 않기 위해
                DFS(i);
                ch[i] = 0;
            }
        }
    }
}

int main(void) {
    int a, b;
    
    scanf("%d%d", &n, &m);
    
    for(int i=0; i<m; i++){
        scanf("%d%d",&a,&b);
        map[a][b] = 1;
    }
    ch[1] = 1;
    DFS(1);
    printf("%d\n", cnt);
    
    return 0;
}
​

n = 정점의 개수, m = 간선의 개수

응용 문제) 백준 1260

www.acmicpc.net/problem/1260

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

int map[30][30], ch[30], cnt = 0;
int n, m, start;

void DFS(int v){            // v -> 정점 번호
    printf("%d ", v);
    
    if(cnt == n) {
        return;
    }
    else {
        for(int i=1; i<=n; i++){
            if(map[v][i] == 1 && ch[i] == 0){
                cnt++;
                ch[i] = 1;                          // 한 번 길 갈 때, 똑같은 곳을 또 방문하지 않기 위해
                DFS(i);
            }
        }
    }
}

int main(void) {
    int a, b;
    
    scanf("%d%d%d", &n, &m, &start);
    
    for(int i=0; i<m; i++){
        scanf("%d%d",&a,&b);
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    ch[start] = 1;
    cnt++;
    DFS(start);
    
    return 0;
}

- map[a][b] 만이 아닌, map[b][a]도 1로 설정

- 시작 정점을 1이 아닌, 값을 받아서 주고,

- 여러 경로를 탐색하기 위해 ch[i] = 0; 으로 풀어주는 과정을 지웠다.

응용문제) 백준 10971

www.acmicpc.net/problem/10971

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int W[11][11];
int visited[11];

int N;
int start;
long long int m = 98765432;

void dfs(int start, int n, int cost, int cnt){
    
    // 선택한 노드의 수가 총 개수이고, 시작 노드까지의 경로가 있으면
    if(cnt == (N-1) && W[n][start] != 0){
        cost += W[n][start];
        if(cost < m)
            m = cost;
        return;
    } else {
        for(int i=0; i<N; i++){
            
            if(n == i || W[n][i] == 0)
                continue;
            
            // 간 적이 없는 노드일 때
            if(visited[i] == 0){
                
                visited[i] = 1;
                dfs(start, i, cost + W[n][i], cnt+1);
                visited[i] = 0;
            }
        }
    }
}


int main(void) {

    scanf("%d", &N);
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &W[i][j]);
        }
    }

    // 0에서 출발하는 것만 구해도 됨 -> 싸이클이 있기 때문에 다른 출발점으로 해도 동일함
    visited[0] = 1;
    dfs(0, 0, 0, 0);
    
    printf("%lld\n", m);
    
    return 0;
}

- 최소 비용 경로를 구하는 문제였음

- DFS 재귀 반복할 때마다 cost와 cnt 를 넣어주고, 나올 때는 다시 풀게 하여 모든 경우의 cost 와 cnt를 구할 수 있게 함