[21.08.23] BFS/ 슬라이딩윈도우 기본

- BFS기본 (배열사용)

#include <iostream>

using namespace std;

char name[6] = "ABCDE";

int map[5][5] = {
        0,1,1,0,0,
        0,0,0,1,1,
        0,0,0,0,0,
        0,0,0,0,0,
        0,0,0,0,0
};

int head = 0, tail = 1;
int queue[11];

int main() {

    queue[0] = 0;
    while (head != tail) {
        int now = queue[head++];

        cout << name[now] << " ";

        for (int i = 0; i < 5; i++) {
            if (map[now][i] == 1) {
                queue[tail++] = i;
            }
        }
    }

    return 0;
}

- BFS기본 (Queue 사용)

#include <iostream>
#include <queue>

using namespace std;

char name[6] = "ABCDE";

int map[5][5] = {
        0,1,1,0,0,
        0,0,0,1,1,
};

queue<int> q;

int main() {

    q.push(0);

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        cout << name[now] << " ";

        for (int i = 0; i < 5; i++) {
            if (map[now][i] == 1) {
                q.push(i);
            }
        }
    }

    return 0;
}

- BFS기본 (인접리스트, Queue사용)

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<vector<int>> vect(5);
char name[6] = "ABCDE";
queue<int>q;

int main() {
    vect[0].push_back(1);
    vect[0].push_back(2);
    vect[1].push_back(3);
    vect[1].push_back(4);

    q.push(0);

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        cout << name[now] << " ";
        for (int i = 0; i < vect[now].size(); i++) {
            int next = vect[now][i];
            q.push(next);
        }
    }

    return 0;
}

- BFS 그래프 1번씩 탐색

#include <iostream>

using namespace std;

char name[6] = "ABCDE";

int map[4][4] = {
    0,1,0,1,
    0,0,1,0,
    1,0,0,1,
    1,0,0,0,
};

struct node {
    int index;
    int level;
}queue[20];

int head = 0, tail = 1;
int used[4];

void bfs() {
    while (head != tail) {
        node now = queue[head++];
        
        cout << name[now.index] << " ";
        
        for (int x = 0; x < 4; x++) {
            if (map[now.index][x] == 1 && used[x] == 0) {
                used[x] = 1;
                queue[tail++] = { x, now.level + 1 };
            }
        }
    }
}

int main() {
    
    queue[0] = { 0,0 };
    used[0] = 1;
    bfs();

    return 0;
}

- BFS A->E 최소이동거리

#include <iostream>

using namespace std;
char name[6] = "ABCDE";
int map[5][5] = {
    0,1,1,0,0,
    0,0,1,1,0,
    0,1,0,1,1,
    0,1,0,0,1,
    0,0,0,0,0,
};

struct node {
    int index;
    int level;
}queue[100] = { 0,0 };

int head = 0, tail = 1;
int used[5]; //싸이클방지 한번씩만 탐색할때

void bfs() {
    while (head != tail) {
        node now = queue[head++];

        if (now.index == 4) { // name[now.index]=='E'
            cout << now.level;
            return;
        }

        for (int i = 0; i < 5; i++) {
            if (map[now.index][i] == 1 && used[i] == 0) {
                used[i] = 1;
                queue[tail++] = { i,now.level + 1 };
            }
        }
    }
}

int main() {
    used[0] = 1;
    bfs();

    return 0;
}

- BFS A->D 갈수있는 경로 몇가지?

#include <iostream>

using namespace std;
char name[6] = "BACD";

int map[4][4] = {
    0,0,1,1,
    1,0,1,0,
    1,0,0,1,
    0,0,0,0,
};

struct node {
    int index;
    int level;
    int used[4];
}queue[100];

int head = 0, tail = 1, cnt = 0;

void bfs() {
    queue[0].index = 1;
    queue[0].used[1] = 1;

    while (head != tail) {
        node now = queue[head++];

        if (now.index == 3) { // name[now.index]=='E'
            cnt++;
        }

        for (int i = 0; i < 4; i++) {
            if (map[now.index][i] == 1 && now.used[i] == 0) {
                queue[tail] = now;
                queue[tail].index = i;
                queue[tail].level = now.level + 1;
                queue[tail].used[i] = 1;
                tail++;
            }
        }
    }
}

int main() {
    bfs();

    cout << cnt;
    return 0;
}

- BFS A->D 갈수있는 모든경로 출력

#include <iostream>

using namespace std;
char name[6] = "ABCD";

int map[4][4] = {
    0,1,1,1,
    0,0,0,1,
    0,0,0,1,
    1,0,1,0,
};

struct node {
    int index;
    int level;
    int used[4];
    char path[10];
}queue[100] = { 0,0,{1},{'A'}};

int head = 0, tail = 1;

void bfs() {
    while (head != tail) {
        node now = queue[head++];

        if (now.index == 3) { // name[now.index]=='E'
            cout << now.path << endl;
        }

        for (int i = 0; i < 4; i++) {
            if (map[now.index][i] == 1 && now.used[i] == 0) {
                queue[tail] = now;
                queue[tail].index = i;
                queue[tail].level = now.level + 1;
                queue[tail].used[i] = 1;
                queue[tail].path[now.level + 1] = name[i];
                tail++;
            }
        }
    }
}

int main() {

    bfs();
    
    return 0;
}

- 연속된 5개의 합을 구하는데, 합이 최대인곳의 좌표 출력 (On2)

#include <iostream>

using namespace std;
char name[6] = "ABCD";

int arr[11] = { 3,17,4,11,1,5,2,3,4,5,7 };

int mmax = 0;
int sum = 0;
int maxindex = 0;

void bfs() {

    for (int i = 0; i < 7; i++) {
        sum = 0;
        for (int j = i; j < i + 5; j++) {
            sum += arr[j];
        }
        if (sum > mmax) {
            mmax = sum;
            maxindex = i;
        }
    }
    
}

int main() {

    bfs();
    
    cout << maxindex;
    return 0;
}

- 연속된 5개의 합을 구하는데, 합이 최대인곳의 좌표 출력 -> 슬라이딩윈도우 (시간복잡도 On)

#include <iostream>

using namespace std;
char name[6] = "ABCD";

int arr[11] = { 3,17,4,11,1,5,2,3,4,5,7 };

int mmax = 0;
int sum = 0;
int maxindex = 0;

void bfs() {

    for (int i = 0; i < 5; i++) {
        sum += arr[i];
    }

    for (int i = 0; i < 6; i++) {
        if (sum > mmax) {
            mmax = sum;
            maxindex = i;
        }
        sum += arr[i + 5];
        sum -= arr[i];
    }
    
}

int main() {

    bfs();
    
    cout << maxindex;
    return 0;
}