[21.08.24] DFS/ BFS/ 슬라이딩윈도우

- tree DFS

#include<iostream> // tree dfs
using namespace std;

char name[6] = "KFCMC";
int map[5][5] = {
//  0 1 2 3 4
    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,
};

void dfs(int now)
{
    cout << name[now]; // 탐색 순서대로 출력

for (int x = 0; x < 5; x++)
{
    if (map[now][x] == 1)
    {
        dfs(x);
    }
}
}
int main()
{

dfs(0); // 탐색 시작하는 인덱스


return 0;
}

- 그래프 (1번씩 탐색) _ used 사용 !! 1로만 켜주기

#include<iostream> 
using namespace std;

char name[5] = "ABCD";
int map[4][4] = {
    0,1,1,0,
    1,0,1,1,
    0,1,0,1,
    0,0,0,0,
};
int used[4];
void dfs(int now)
{
    cout << name[now]<<" ";
    for (int x = 0; x < 4; x++)
    {
        if (map[now][x] == 1&&used[x]==0)
        {
            used[x] = 1;
            dfs(x);
        }
    }
}
int main()
{
    used[1] = 1;
    dfs(1);  // 시작인덱스
}

- dfs 경로탐색 (출발지 도착지 입력)

#include<iostream> 
using namespace std;

char name[5] = "ABCD";
int map[4][4] = {
    0,1,1,0,
    0,0,1,1,
    0,1,0,1,
    0,0,0,0,
};
int used[4];
char start, dochak;
int startindex, endsindex;
int cnt = 0;
void dfs(int now)
{

// if(now==endsindex)
if (name[now] == dochak)
{
    cnt++;
}
for (int x = 0; x < 4; x++)
{
    if (map[now][x] == 1 && used[x] == 0)
    {
        used[x] = 1;
        dfs(x);
        used[x] = 0;
    }
}
}
int main()
{

    cin >> start >> dochak; // 시작점 도착점
    for (int x = 0; x < 4; x++)
    {
        if (name[x] == start)
        {
            startindex = x;
        }
        if (name[x] == dochak)
        {
            endsindex = x;
        }
    }

used[startindex] = 1;
dfs(startindex);
cout << cnt;
}

- tree bfs

#include<iostream> // tree bfs
using namespace std;

char name[6] = "KFMCC";
int map[5][5] = {
    0,1,0,0,1,
    0,0,1,1,0,
    0,0,0,0,0,
    0,0,0,0,0,
    0,0,0,0,0,
};
struct node {
    int index;
    int level;
};
node queue[10] = { 0,0 };
int head = 0;
int tail = 1;
int main()
{
    while (head != tail)
    {
        node now = queue[head++];  // queue[0].index=0  //  queue[0].level =0;

    cout<<name[now.index];

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

- bfs 그래프 탐색

#include<iostream>  // bfs 그래프 탐색 
using namespace std;
char name[6] = "KMSTY";
int map[5][5] = {
    0,1,1,1,0,
    0,0,1,0,0,
    1,0,0,1,1,
    0,0,0,0,1,
    0,0,0,0,0,
};
struct node {
    int index;
    int level;
};
node queue[100];
int used[5];
int head = 0, tail = 1;
int main()
{
    queue[0] = {1,0}; // 1번 인덱스 부터 bfs 탐색
    used[1] = 1;

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

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

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

return 0;
}

- 슬라이딩윈도우 (민코딩) https://pro.mincoding.co.kr/problem/SDS_%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9%EC%9C%88%EB%8F%84%EC%9A%B0

OnlineJudge

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int n, w;
vector<int> img;

int sum, mmax, maxin;

void run() {
    img.clear();
    
    sum = 0;
    mmax = -21e8;
    maxin = 0;

    cin >> n >> w;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        img.push_back(num);
        if(i<w)
            sum += img[i];
    }

    for (int i = 0; i <= n-w; i++) { //i<n-w시 마지막자리 max 비교를 못함
        if (mmax < sum) {
            mmax = sum;
            maxin = i;
        }
        
        if (i == n - w) break; //마지막자리까지 비교후 sum실행시 오류로 break

        sum += img[i + w];
        sum -= img[i];
    }

}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        run();
        cout << "#" << i + 1 << " "
            << maxin << " " << maxin + (w-1)
            << " " << mmax;
        cout << endl;
    }

    return 0;
}

- 슬라이딩윈도우 (민코딩 예식장서빙)

https://pro.mincoding.co.kr/problem/SDS_%EC%98%88%EC%8B%9D%EC%9E%A5%EC%84%9C%EB%B9%99

OnlineJudge

-> 원형을 1차원배열로 복사하기

//교수님 코드
#include<iostream>
using namespace std;
int main()
{
    int n = 8;//음식 개수
    int r = 2;//범위 거리
    int arr_temp[] = { 65, 65, 81, 66, 65, 65, 69, 69 };
    int arr[16] = { 0 }; // 0~7 인덱스 원본 8~15 인덱스 까지 복사본

for (int x = 0; x < 8; x++)
{
    arr[x] = arr_temp[x];
    arr[x + n] = arr[x];
}

// 로테이션 준비
// 원하는것 은 : 각 음식이 몇개씩 있는가??  3개 이상이면 땡

int dat[201] = { 0 };
int check = 0;

// 슬라이딩 윈도 해주는데 확인할 구간은
// 2*r +1개 를 확인

for (int x = 0; x < 2 * r; x++)
{
    //2*r개에 대한 처리
    dat[arr[x]]++;
    if (dat[arr[x]] >= 3)
    {
        check = 1;
    }
}

for (int x = 0; x < n; x++)
{
    //2*r 개-> 2*r+1개를 확인

    dat[arr[x + 2 * r]]++;
    // 2*r+1개의  음식에 대한 처리

    if (dat[arr[x + 2 * r]] >= 3) {
        check = 1;
    }
    // 다음 구간에 겹치는 음식만 남기기 위해서

    // 현재 구간의 맨앞 data를 삭제

    dat[arr[x]]--;
}


if (check == 1)cout << "노";
else cout << "예스";

return 0;
}

- TC 부분 실패

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int n, r;
vector<int> menu;
int sum, mmax, maxin;

bool run() {
    menu.clear();

    sum = 0;
    mmax = -21e8;
    maxin = 0;


    int dat[200] = { 0 };

    cin >> n >> r;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        menu.push_back(num);
    }

    for (int i = 0; i <= 2 * r; i++) {
        dat[menu[i]]++;
        if (dat[menu[i]] > 2) return false;
    }

    int s = 2 * r + 1;
    for (int i = 0; i < r; i++) {
        dat[menu[s+i]]++;
        dat[menu[i]]--;
        if (dat[menu[s + i]]>2) return false;

    }

    return true;
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        if (run())
            cout << "#" << i + 1 << " " << "YES" << endl;
        else
            cout << "#" << i + 1 << " " << "NO" << endl;
    }

    return 0;
}