[백준/C++]#1260 - DFS와 BFS

풀이

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

vector<int> a[1001];	// 저장공간 정의
bool check[1001];

void dfs(int node) {
    check[node] = true;		// 왔다감 체크
    cout << node << " ";
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (check[next] == false) {		// 체크 확인
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    check[start] = true;
    q.push(start);
    while (!q.empty()) {	// queue가 빌 때까지
        int node = q.front();
        q.pop();
        cout << node << " ";
        for (int i=0; i<a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) {		// 체크 확인
                check[next] = true;		// 왔다감 체크
                q.push(next);
            }
        }
    }
}

int main() {
    int n, m, start;
    cin >> n >> m >> start;
    for (int i=0; i<m; i++) {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for (int i=1; i<=n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    dfs(start);
    cout << '\n';
    memset(check,false,sizeof(check));
    bfs(start);
    return 0;
}

개념

cstring 라이브러리에 있는 memset(a,b, sizeof(a)) 함수를 사용한다.

이는 메모리 내용을 원하는 크기만큼 특정 값으로 setting 할 수 있는 함수이다.

원하는 메모리의 주소를 a에 넣고, 세팅하고자 하는 값을 b에 넣는다.

그리고 바꿀 메모리의 바이트를 3번째 항에 적는데, 보통 sizeof()를 사용한다.

 

vector<int> a[1001] 은 vector<int> a(1001) 와 전혀 다르다.

이는 vector <int> a 를 1001개 만드는 방식이다.  각각의 저장공간을 사용할 수 있으므로, 인접 리스트 문제에서 이를 정점으로 두고 간선을 저장 할 때 활용된다.

 

vector에서 값을 추가할 때, .push_back()을 사용해 마지막 위치에 값을 저장할 수 있다.

또는 .index(a,b)를 사용해 index a 위치에 b를 저장하는 것도 가능하다.

 

---

풀이

두개의 공간을 정의하는데, 하나는 정점의 인접리스트(간선)를 저장할 공간이다.

이는 vector <int > a[1001]로 정의한다.

두 번째 공간은 check[1001] 배열이다. 이는 해당 정점을 방문했는지 확인할 수 있게 bool 자료형을 사용한다.

 

각 정점에 해당하는 간선을 입력받을 때, 반드시 이 입력이 순서대로 입력되는 보장이 없다. 

따라서 sort함수를 사용해 모든 정점에 해당하는 리스트를 정렬해야한다.

 

DFS 예시

dfs는 연결된 첫번째 노드를 통해 다른 노드로 끝까지 갔다가, 더이상 진척이 없으면 stack에 쌓인 부분을 순서대로 다시 방문하는 방식이다. 방문한 node는 체크하고, 출력한다.

한 node에 해당하는 인접 리스트의 수만큼 반복문이 이뤄지고, 인접한 리스트에 방문하지 않았다면 방문한다.

이를 순환호출로 나타낼 수 있다.

 

BFS 예시

bfs는 한 노드에 연결된 모든 노드에 방문 한 뒤, queue에 들어온 순서대로 다음 노드를 다시 방문하는 방식이다.

방문한 node는 체크하고, 출력한다.

한 node에 해당하는 인접 리스트의 수만큼 반복문이 이뤄지고, 인접한 리스트에 방문하지 않았다면 체크한 뒤 방문한다.

 

main 함수에서 dfs()를 실행한뒤, check 배열을 초기화하지않으면 bfs()를 할 수 없다.

따라서 사용 후 memset() 함수를 사용한다.

 

---

+a

다른풀이①(from 백준github)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct Edge {
    int from, to;
};
Edge edge[20001];
int cnt[1001];
bool check[1001];
bool cmp(const Edge &u, const Edge &v) {
    if (u.from == v.from) {
        return u.to < v.to;
    } else {
        return u.from < v.from;
    }
}
void dfs(int node) {
    check[node] = true;
    printf("%d ",node);
    for (int i=cnt[node-1]; i<cnt[node]; i++) {
        int next = edge[i].to;
        if (check[next] == false) {
            dfs(next);
        }
    }
}
void bfs(int start) {
    queue<int> q;
    q.push(start);
    check[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        printf("%d ",node);
        for (int i=cnt[node-1]; i<cnt[node]; i++) {
            int next = edge[i].to;
            if (check[next] == false) {
                check[next] = true;
                q.push(next);
            }
        }
    }
}
int main() {
    int n, m, start;
    scanf("%d %d %d",&n,&m,&start);
    for (int i=0; i<m; i++) {
        scanf("%d %d",&edge[i].from, &edge[i].to);
        edge[i+m].from = edge[i].to;
        edge[i+m].to = edge[i].from;
    }
    m *= 2;
    sort(edge, edge+m, cmp);
    for (int i=0; i<m; i++) {
        cnt[edge[i].from] += 1;
    }
    for (int i=1; i<=n; i++) {
        cnt[i] += cnt[i-1];
    }
    dfs(start);
    printf("\n");
    memset(check,false,sizeof(check));
    bfs(start);
    printf("\n");
    return 0;
}

구조체를 사용한 방식이다.

간선 리스트를 활용하고, cnt[] 배열도 사용한다.

 

다른풀이②(from 백준github)

#include <cstdio>
#include <stack>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[1001];
bool check[1001];
void dfs(int node) {
    stack<pair<int,int>> s;
    s.push(make_pair(node,0));
    check[node] = true;
    printf("%d ",node);
    while (!s.empty()) {
        int node = s.top().first;
        int start = s.top().second;
        s.pop();
        for (int i=start; i<a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) {
                printf("%d ",next);
                check[next] = true;
                s.push(make_pair(node,i+1));
                s.push(make_pair(next,0));
                break;
            }
        }
    }
}
void bfs(int start) {
    queue<int> q;
    memset(check,false,sizeof(check));
    check[start] = true;
    q.push(start);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        printf("%d ",node);
        for (int i=0; i<a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) {
                check[next] = true;
                q.push(next);
            }
        }
    }
}
int main() {
    int n, m, start;
    scanf("%d %d %d",&n,&m,&start);
    for (int i=0; i<m; i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for (int i=1; i<=n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    dfs(start);
    puts("");
    bfs(start);
    puts("");
    return 0;
}

dfs를 재귀 호출을 사용하지 않고 구현한다.

bfs에서 queue를 사용한 것처럼, 해당 스택이 빌 때까지 반복하며 탐색한다.