[21.08.06]DFS, BFS + 문제풀이

- 민코딩 (구현의탑_흑돌백돌)

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

char arr[8][8];

void check(int y, int x, char stone) {    //돌 놓은좌표, 내 돌의 색상

char bande = '@';
if (stone == '@')  bande = 'O';

vector<pair<int, int>> vect;

int direction[8][2] = { -1,-1,1,1,-1,1,1,-1,1, 0, -1, 0, 0, 1, 0, -1 };

for (int t = 0; t < 8; t++) {
    int dy = y + direction[t][0];
    int dx = x + direction[t][1];
    int flag = 0;
    vect.clear();
    // 배열범위
    if (dy < 0 || dy >= 8 || dx < 0 || dx >= 8) continue;

    // 내돌 옆에 반대다
    if (arr[dy][dx] == bande) { 
        while (1) {  // 계속 옆을 보자
            if (arr[dy][dx] == bande) {  
                vect.push_back({ dy, dx });
                dy = dy + direction[t][0];
                dx = dx + direction[t][1];
                
                // 범위 밖이거나 돌이 없는 경우에는 break
                if (dy < 0 || dy >= 8 || dx < 0 || dx >= 8 || arr[dy][dx] == '_') {
                    flag = 0;
                    break;
                }
            }
            // 상대 돌이 나오다가 내 돌이 나온다면 true
            else if (arr[dy][dx] == stone) {
                flag = 1;
                break;
            }
        }
    }
    if (flag==1) {
        for (int y = 0; y < vect.size(); y++) {
            arr[vect[y].first][vect[y].second] = stone;
        }
    }
}
}

int main() {

int n;
cin >> n;
int y, x;

for (int y = 0; y < 8; y++) {
    for (int x = 0; x < 8; x++) {
        arr[y][x] = '_';
    }
}


for (int t = 0; t < n; t++) {

    cin >> x >> y; // 3,4
    char stone;
    if (t % 2 == 0) stone = '@';
    else stone = 'O';
    arr[7 - y][x] = stone;  // 4,3  돌 놓고 체크
    check(7 - y, x, stone); 
}


for (int y = 0; y < 8; y++) {
    for (int x = 0; x < 8; x++) {
        cout << arr[y][x];
    }
    cout << endl;
}

return 0;
}

- 백준_봄버맨(https://www.acmicpc.net/problem/16918)

#include <vector>

#include <string>

#include <queue>

#include <iostream>
using namespace std;

int r, c, n;
char map[200][200];
int direct[4][2] = {
    0,1,
    0,-1,
    1,0,
    -1,0
};

int main() {
    cin >> r >> c >> n;

for (int y = 0; y < r; y++) {  // 입력
    for (int x = 0; x < c; x++) {
        cin >> map[y][x];
    }
}


if (n % 2 == 0) {    // N이 2의 배수라면 항상 모든 판에 폭탄으로 채워진 상태임
    for (int y = 0; y < r; y++) {
        for (int x = 0; x < c; x++) {
            cout << 'O';
        }
        cout << '\n';
    }
    return 0;
}


int time = 1;

while (time != n) {

    /*
    struct node {
        int a, b;
    };
    */

    queue<pair<int, int>> q;     // 구조체로 사용하셔도 좋습니다. pair는 두개의 변수를 하나 로 묶어서 사용한다는 것으로 차후 라이브때 볼께요~
    //queue<node>q;

    for (int y = 0; y < r; y++) {         // 'O'으로 모두 채우고 queue에 폭탄좌표 저장
        for (int x = 0; x < c; x++) {
            if (map[y][x] == 'O') q.push({ x, y });
            else map[y][x] = 'O';
        }
    }


    while (!q.empty()) {         // 터트리기
        int x = q.front().first;  // pair 자료형의 앞부분을 first  구조체라면 x=q.front().a;
        int y = q.front().second; // pair 자료형의 뒷부분을 second 로 놓았습니다.  구조체라면 x=q.front().b;
        q.pop();

        map[y][x] = '.';
        for (int t = 0; t < 4; t++) {
            int dy = x + direct[t][1];
            int dx = y + direct[t][0];

            if (dy >= 0 && dy < c && dx >= 0 && dx < r) {
                map[dx][dy] = '.';  // 터트리기
            }
        }
    }
    time += 2;
}


for (int y = 0; y < r; y++) {  // 출력
    for (int x = 0; x < c; x++) {
        cout << map[y][x];
    }
    cout << '\n';
}
}

- 배열덧셈(자릿수 올림)

#include<iostream>
using namespace std;

void input(char arr[6])
{
    for (int x = 0; x < 6; x++)
        cin >> arr[x];
}

int main()
{
    char arr1[6], arr2[6], sum[6] = {0};
    input(arr1);
    input(arr2);

int flag;
for (int x = 5; x >= 0; x--)
{
    flag = 0;
    if ((arr1[x] - '0') + (arr2[x] - '0') >= 10)    // 합이 10이 넘을때
    {
        sum[x] += (arr1[x] - '0') + (arr2[x] - '0') - 10;
        flag = 1;
    }
    else {   // 합이 10이 안넘을떄
        sum[x] += (arr1[x] - '0') + (arr2[x] - '0');
    }

    if (flag == 1) sum[x - 1]++; // 10이 넘으면 앞자리 ++
}

for (int x = 0; x < 6; x++)
    cout << sum[x] << ' ';

return 0;
}

- BFS + cycle방지(used)

#include <iostream>
#include <queue>
using namespace std;

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

char name[8] = "AGKRHTV";
int used[10];

queue<int> q;

int main()
{
    used[2] = 1;
    q.push(2);

    while (!q.empty()) {

        int now = q.front();
        q.pop();

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

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

    return 0;
}

- Node사용하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

struct Node {
    int n;
};

queue<Node> q;

int main()
{
    q.push({ 0 });

    while (!q.empty())
    {
        //1. 하나 뺸다. 
        Node now = q.front();
        q.pop();

        cout << now.n << " ";

        //2. now에서 다음 갈수있는길을 다 예약건다.
        for (int i = 0; i < 6; i++) {
            if (map[now.n][i] == 0) continue;
            q.push({ i });
        }
    }

    return 0;
}

- 그래프 DFS

#include <iostream>
#include <vector>
using namespace std;

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

void run(int now)
{
    cout << now << " ";
    for (int i = 0; i < 4; i++) {
        if (map[now][i] == 0) continue;
        if (used[i] == 1) continue;
        used[i] = 1;
        run(i);
    }
}

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

    return 0;
}

- 인접리스트 탐색

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> alist(9);
int val[9] = { 0, 1, 2, 7, 3, 6, 9, 15, 16 };

void run(int now)
{
    cout << val[now] << " ";
    for (int i = 0; i < alist[now].size(); i++) {

        int next = alist[now][i];
        run(next);

    }
}

int main()
{
    alist[0] = { 1, 2, 3 };
    alist[2] = { 4, 5 };
    alist[3] = { 6, 7, 8 };
    
    run(3);

    return 0;
}

- DFS

#include <iostream>
#include <vector>
using namespace std;

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

void run(int now)
{
    cout << now << " ";
    for (int i = 0; i < 6; i++) {
        if (map[now][i] == 0) continue;
        run(i);
    }
}

int main()
{
    run(0);

    return 0;
}

- 인접행렬/ 인접리스트로 풀어보기

#include <iostream>
#include <vector>
using namespace std;

char name[8] = "AGBTRSV";
int map[8][8] = {
    0,1,1,1,0,0,0,
    0,0,0,0,1,1,0,
    0,0,0,0,0,0,0,
    0,0,0,0,0,0,1,
};

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < 8; i++) {
        if (map[n][i] == 0) continue;
        cout << name[i];
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

char name[8] = "AGBTRSV";
vector<vector<int>> alist(7);

int main()
{
    alist[0] = { 1, 2, 3 };
    alist[1] = { 4, 5 };
    alist[3] = { 6 };

    int n;
    cin >> n;

    for (int i = 0; i < alist[n].size(); i++) {
        cout << name[alist[n][i]];
    }

    return 0;
}

- 인접리스트활용 탐색

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> alist(4);
int name[4] = { 3, 5, 4, 0 };

int main()
{
    /*alist[0].push_back(1);
    alist[0].push_back(2);
    alist[0].push_back(3);
    alist[1].push_back(3);
    alist[2].push_back(3);
*/
    alist[0] = { 1, 2 };
    alist[1] = { 3 };
    alist[2] = { 3 };

    int n;
    cin >> n;

    for (int i = 0; i < alist[n].size(); i++) {
        cout << name[alist[n][i]];
    }

    return 0;
}

- vector활용법

#include <iostream>
#include <vector>
using namespace std;

//1차원 배열 같은 객체 t를 만듬
//만들어진 칸 수는 = 0칸
vector<int> t;

//1차원 배열 같은 객체 v하나 생성
//만들어진 칸 수는 = 다섯 칸
vector<int> v(5);

int main()
{
    t[1] = 15; //이건 에러 (만들어진 칸이 없음)
    v[1] = 15; //이건 가능

    t.push_back(1);
    t.push_back(2);
    t.push_back(3);

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v;
vector<int> g;

int main()
{
    //g 에 한칸 추가 (3이 들어감)
    g.push_back(3);
    g.push_back(4);

    //v에 한칸 추가
    v.push_back({ 1, 2, 3 });
    v.push_back({ 9, 7 });

    return 0;
}

- 인접행렬이용한 탐색

#include <iostream>
using namespace std;

char name[6] = "ABCDF";
int map[5][5] = {
    0,0,0,1,0,
    1,0,0,1,0,
    0,0,0,1,0,
    0,0,0,0,1,
    0,1,1,0,0,
};

int main()
{
    int max = 0;
    char maxCh;
    for (int x = 0; x < 5; x++) {
        int cnt = 0;
        for (int y = 0; y < 5; y++) {
            if (map[y][x] == 0) continue;
            cnt++;
        }

        if (max < cnt) {
            max = cnt;
            maxCh = name[x];
        }
    }

    cout << maxCh;

    return 0;
}

- 배열과 링크드리스트 탐색 -> 추후 진행 예정

#include <iostream>
using namespace std;

struct Node {
    int n;
    Node *next;
};

Node *head, *last;

void addNode(int n)
{
    if (head == NULL) {
        head = new Node();
        head->n = n;
        last = head;
        return;
    }

    last->next = new Node();
    last = last->next;
    last->n = n;
}

int main()
{
    int v[5] = { 4, 8, 7, 6, 9 };

    addNode(4);
    addNode(8);
    addNode(7);
    addNode(6);
    addNode(9);

    for (int i = 0; i < 5; i++) {
        cout << v[i];
    }
    cout << endl;
    for (Node *p = head; p != NULL; p = p->next) {
        cout << p->n;
    }

    return 0;
}