[Baekjoon] 백준 민식우선탐색(1376번) 문제풀이(C++)

재귀를 이용한 구현

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
bool visited[100001];
struct Vertex {
    int num;
    vector<int> edges;
    Vertex(int n) {
        num = n;
    }
};
vector<Vertex> List;
 
void mFS(int num) {
    if (visited[num]) return;
    visited[num] = true;
    cout << num << " ";
    vector<int> numset;
 
 
    while (1) {
        numset.clear();
        for (int i = 0; i < List[num].edges.size(); i++) {
            if (!visited[List[num].edges[i]])
                numset.push_back(List[num].edges[i]);
        }
 
        if (numset.size() == 0) return;
        if (numset.size() % 2 == 1) {
            mFS(numset[numset.size() / 2]);
        }
        else {
            mFS(numset[0]);
        }
 
    }
}
 
int main() {
 
    for (int i = 0; i < 100001; i++) {
        visited[i] = false;
    }
    visited[0] = true;
    int N, M; cin >> N >> M;
 
    Vertex* a = new Vertex(0);
    List.push_back(*a);
 
    for (int i = 1; i <= N; i++) {
        Vertex* a = new Vertex(i);
        List.push_back(*a);
    }
 
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        List[a].edges.push_back(b);
        List[b].edges.push_back(a);
    }
 
    for (int i = 1; i <= N; i++) {
        sort(List[i].edges.begin(), List[i].edges.end());
    }
 
    for (int i = 1; i <= N; i++) { //
        for (int j = 0; j < List[i].edges.size() - 1; j++) {
            if (List[i].edges.size() <= 1) break;
            if (List[i].edges[j] == List[i].edges[j + 1])
            {
                List[i].edges.erase(List[i].edges.begin() + j);
                j--;
            }
        }
    }
    mFS(1);
 
    cout << endl;
    return 0;
}