그래프(DFS, BFS)

DFS(Deep First Search) 깊이 우선 탐색    BFS(Breadth First Search) 너비 우선 탐색                인접행렬

      

2606번 문제 : 바이러스

https://www.acmicpc.net/problem/2606

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int const MAX_VALUE = 101;
int matrix[MAX_VALUE][MAX_VALUE] = { 0 };
bool visit[MAX_VALUE] = { false };
int counter = 0;
 
void DFS(int v, int N) {
    if(visit[v] != true)
        counter++;
 
    visit[v] = true;
    
    for (int i = 1; i <= N; i++)
    {
        if (matrix[i][v] == 0 || visit[i] == true)
            continue;
 
        DFS(i, N);
    }
}
 
int main()
{
    int N, M;
    cin >> N >> M;
 
    for (int i = 1; i <= M; i++)
    {
        int x, y;
        cin >> x >> y;
        matrix[x][y] = matrix[y][x] = 1;
    }
 
    DFS(1, N);
 
    cout << counter - 1 << endl;
 
    return 0;
}
 

메모:

-중복체크를 하면서 count해야함

2309번 문제 : 순열 사이클

https://www.acmicpc.net/problem/10451

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int const MAX_VALUE = 1001;
int matrix[MAX_VALUE][MAX_VALUE] = { 0 };
int visit[MAX_VALUE] = { 0 };
int index = 0;
vector<int> result;
 
void DFS(int v, int N, int index) {
    visit[v] = index;
    for (int i = 1; i <= N; i++)
    {
        if (matrix[i][v] != index || visit[i] == index)
            continue;
 
        DFS(i, N, index);
    }
}
 
int main()
{
    int num;
    cin >> num;
 
    while (num > 0)
    {
        int M; 
        cin >> M;
        int counter = 0;
        index++;
 
        for (int i = 1; i <= M; i++)
        {
            int x = i;
            int y;
            cin >> y;
            matrix[x][y] = matrix[y][x] = index;
        }
 
        for (int i = 1; i <= M; i++)
        {
            if (visit[i] != index)
            {
                DFS(i, M, index);
                counter++;
            }
        }
        result.push_back(counter);
        num--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
    return 0;
}

메모:

-matrix를 사용 후에 초기화 하는 방식으로 하면 시간 초과 발생 -> index를 활용하여 기존의 matrix를 재활용

-아래 코드는 코드를 이해하는데 더 직관적이나 initializing하는 과정(시간복잡도: O (n ²)) 때문에 시간초과 발생

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int const MAX_VALUE = 1001;
int matrix[MAX_VALUE][MAX_VALUE] = { 0 };
bool visit[MAX_VALUE] = { 0 };
vector<int> result;
int counter = 0;
 
void DFS(int v, int N) {
    //    cout << v << " "; //for debug
    visit[v] = true;
    for (int i = 1; i <= N; i++)
    {
        if (matrix[i][v] == 0 || visit[i] == true)
            continue;
 
        DFS(i, N);
    }
}
 
void InitializeMatrix()
{
    for (int i = 0; i < MAX_VALUE; i++)
    {
        for (int j = 0; j < MAX_VALUE; j++)
        {
            matrix[i][j] = 0;
        }
    }
 
    for (int i = 0; i < MAX_VALUE; i++)
    {
        visit[i] = false;
    }
 
    counter = 0;
}
 
int main() //시간초과 발생하는 코드
{
    int num;
    cin >> num;
 
    while (num > 0)
    {
        int M;
        cin >> M;
 
        InitializeMatrix();
 
        for (int i = 1; i <= M; i++)
        {
            int x = i;
            int y;
            cin >> y;
            matrix[x][y] = matrix[y][x] = 1;
        }
 
        /*
        //Matrix Debug
        cout << endl;
        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                cout << matrix[i][j] << "  ";
            }
            cout << endl;
        }
        cout << endl;
        */
 
        for (int i = 1; i <= M; i++)
        {
            if (visit[i] != true)
            {
                DFS(i, M);
                counter++;
            }
        }
 
        result.push_back(counter);
        num--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
    return 0;
}