알고리즘

BOJ #1260 : DFS와 BFS

2019년 01월 14일

DFS

int dfs(int pos)
{
    printf("%d ", pos);
    visited[pos] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (visited[i] == 0 && edge[pos][i] > 0) dfs(i);
    }    
}

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.

BFS

int bfs(int pos)
{
    int x;
    queue<int> q;
    q.push(pos);
    visited[pos] = 1;
    while(!q.empty())
    {
        x = q.front();
        printf("%d ", x);
        q.pop();
        for (int i = 1; i <= n; i++)
        {
            if (edge[x][i] > 0 && visited[i] == 0){
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}

1260번 : 문제풀이

#include <cstdio>
#include <cstring>
#include <queue>


using namespace std;

int edge[1001][1001];
int visited[1001];
int n, m, v;

int dfs(int pos);
int bfs(int pos);

int main()
{
    int a, b;
    memset(edge, 0,sizeof(edge));
    memset(visited, 0, sizeof(visited));
    scanf("%d %d %d", &n, &m, &v);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d\n", &a, &b);
        edge[a][b] += 1;
        edge[b][a] += 1;
    }
    dfs(v);
    memset(visited, 0, sizeof(visited));
    printf("\n");
    bfs(v);
}
int dfs(int pos)
{
    printf("%d ", pos);
    visited[pos] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (visited[i] == 0 && edge[pos][i] > 0) dfs(i);
    }    
}

int bfs(int pos)
{
    int x;
    queue<int> q;
    q.push(pos);
    visited[pos] = 1;
    while(!q.empty())
    {
        x = q.front();
        printf("%d ", x);
        q.pop();
        for (int i = 1; i <= n; i++)
        {
            if (edge[x][i] > 0 && visited[i] == 0){
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}

벡터를 도입한 코드

정답을 맞추기 위해서는 각 벡터들을 sort해줘야 합니다. 아니면 auto 키워드를 사용하지 않으면 됩니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

int visited[1001];
int n, m, v;
vector<int> edge[1001];

int dfs(int pos);
int bfs(int pos);


int main()
{
    int a, b;
    memset(visited, 0, sizeof(visited));
    scanf("%d %d %d", &n, &m, &v);

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    for (int i = 0; i < n; i++)
    {
        if(edge[i].size())
        {
            sort(edge[i].begin(), edge[i].end());
        }
    }

    dfs(v);
    memset(visited, 0, sizeof(visited));
    printf("\n");
    bfs(v);
}

int dfs(int pos)
{
    visited[pos] = 1;
    printf("%d ", pos);    
    for (auto next : edge[pos])
    {
        if (visited[next] == 0) dfs(next);
    }
}

int bfs(int pos)
{
    queue<int> q;
    q.push(pos);
    visited[pos] = 1;
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
	    printf("%d ", now);
        for (auto next : edge[now])
        {
            if (visited[next] == 0)
            {
                visited[next] = 1;
                q.push(next);
            }
        }
    }
}

← Top