[백준/BOJ] - 1260번 DFS와 BFS (C++/DFS BFS)

 

01. 문제

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

---

 

 

 

 

 

 

문제설명

1. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

2. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

 

---

 

 

02. 문제 접근 과정 📖

예제 입력에서 인접 행렬 방식이 아닌 인접 리스트 방식으로 주므로 Vector로 만들어서 받으면 될 것 같다.

그 후 인접 리스트로 구현된 노드들을 DFS BFS 돌리면 될듯

*간선 양방향 이므로 주의하자

 

 

 

 

---

 

03. 문제 풀이 ✏️

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

int N, M, V;

int Node, Val;

vector<int> graph[1001];
bool visit[1001]{ false, };

void dfs(int _x)
{
    visit[_x] = true;

    cout << _x << ' ';

    for(auto& x : graph[_x])
    {
	    if(!visit[x])
	    {
            dfs(x);
	    }
    }
}

void bfs(int _x)
{
    queue<int> q;

    q.push(_x);

    while (!q.empty())
    {
        int temp = q.front();
        q.pop();
        visit[temp] = true;

        cout << temp << ' ';

        for(auto& x : graph[temp])
        {
            if(!visit[x])
            {
                q.push(x);
                visit[x] = true;
            }
        }
    }

}


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> V;

    for(int i=0; i<M; ++i)
    {
        cin >> Node >> Val;

        graph[Node].push_back(Val);
        graph[Val].push_back(Node);


    }

    for (int i = 1; i <= N; ++i) {
        sort(graph[i].begin(), graph[i].end());
    }


    dfs(V);

    //memset(visit, false, sizeof(visit));
    fill_n(visit, 1001, false);

    cout << '\n';

    bfs(V);

    return 0;
}

 

위에 처럼 풀었지만 메모리를 너무 잡아먹는다!

그래서 조금 최적화는 한다면

1. 배열을 다이나믹으로 설정해서 노드 수에 맞게 벡터 동적으로 설정하자

 

 

03.1 최적화 풀이 ✏️

 

인접 리스트 방식에서 인접 행렬 방식으로 변경하면.. 쪼금 빨리질것 같지만 유의미한 차이는 없을 것 같다.

 

배열을 다이나믹으로 식으로 변경하면.. 더 느려질것 같지만 최적화 관점에서는 더 좋으므로..

여기서 M과 N 값이 다를 수 있다는 관점이 있다

이러면 graph는 1000까지 도는데 visit은 overflow 나므로 visit은 고정으로 1001로 설정하자~

 

 

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

int N, M, V;

int Node, Val;

vector<vector<int>> graph;
vector<bool> visit{ false, };

void dfs(int _x)
{
    visit[_x] = true;

    cout << _x << ' ';

    for( auto& x : graph[_x])
    {
	    if(!visit[x])
	    {
            dfs(x);
	    }
    }
}

void bfs(int _x)
{
    queue<int> q;
    q.push(_x);
    visit[_x] = true;


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

        cout << temp << ' ';

        for(auto& x : graph[temp])
        {
            if(!visit[x])
            {
                q.push(x);
                visit[x] = true;
            }
        }
    }

}


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> V;

    graph.resize(N + 2);
    visit.resize(1001);

    for(int i=0; i<M; ++i)
    {
        cin >> Node >> Val;

        graph[Node].push_back(Val);
        graph[Val].push_back(Node);
    }

    for (int i = 1; i <= N; ++i) {
        sort(graph[i].begin(), graph[i].end());
    }


    dfs(V);

    //memset(visit, false, sizeof(visit));
    //fill_n(visit, 1001, false);
    fill(visit.begin(), visit.end(), false);

    cout << '\n';

    bfs(V);

    return 0;
}

 

여기서 신기한게 vector<bool> 을 fill_n 으로 초기화 시킬 수 없었다.....
fill_n 으로 visit vect를 초기화 시키면 해당 오류가 난다.

'초기화 중': 'const _Diff'에서 '__int64'(으)로 변환할 수 없습니다.

이유를 조금 설명하자면...

다들 아시다 시피 std::vector는 다이나믹 타입으로 T 타입인데, vector<bool> 은 메모리 효율성을 위해서 위 방식을 사용하지 않는다...
그래서 한 바이트에 여러 개의 불리언 값을 저장하는 방식으로 구현된다. (와우)

vector<bool>은 bool 요소를 효율적으로 저장하기 위해 실제 bool 변수가 아닌 특수한 proxy 객체로 사용한다 그리고 이걸 인터페이스로 우리에게 제공한다 여기서!

bool& , const bool& 을 반환하는게 아니라

std::vector<bool>::reference 를 반환한다!

fill_n 함수는 iterator를 지원하지 않으므로 fill로 해야한다....

 

 

 

---

04. 결론

fill_n 이 참 신기하네요..