1389_케빈 베이컨의 6단계 법칙

케빈 베이컨의 6단계 법칙

문제 링크: https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

 

문제를 읽고 그래프의 BFS문제임을 이해했다. 그리고 하나의 VERTEX를 기준으로 Level을 구해 해당 Level의 값들을 모두 더하고 그 값이 가장 작은 값의 노드를 출력한다.

현재 이 코드는 잘못 설계가 되었다.
할당 연산자를 통해 객체를 생성하고 주소를 push저장해주어서 데이터의 깊은복사들이 상당히 까다롭다.
한번 BFS를 돌고 난 후 다시 돌 때 초기 데이터가 백업이 되어있어야 하는데, 모두 주소로 지정한 탓에 깊은 복사가 현재 까다로운 상태이다.

 

• 미해결 코드

    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
  
    #define matSize 101
  
    class user {
    public:
        vector<user*> adj;
        int cur;
        int BFScount;
        bool visited;
        user(int n) {
            this->cur = n;
            this->BFScount = 0;
            this->visited = false;
        }
        operator int() {
            return cur;
        }
        bool operator<(const user& rhs) const {
            return this->cur < rhs.cur;
        }
    };
  
    class graph {
    private:
        vector<user*> userList;
        queue<user*> BFS_Q;
        bool** matrix;
    public:
        graph() {
            this->matrix = new bool* [matSize];
            for (int i = 0; i < matSize; i++) {
                this->matrix[i] = new bool[matSize];
            }
  
            for (int i = 0; i < matSize; i++)
                for (int k = 0; k < matSize; k++)
                    this->matrix[i][k] = false;
  
        }
        user* find_node(int n) {
            for (auto iter = userList.begin(); iter != userList.end(); ++iter)
                if ((*iter)->cur == n)
                    return (*iter);
  
            return NULL;
        }
        void insert_edge(int n, int m) {
  
            auto Pn = find_node(n);
            auto Pm = find_node(m);
  
            if (Pn == nullptr) {
                user* temp_n = new user(n);
                Pn = temp_n;
                userList.push_back(temp_n);
            }
            if (Pm == nullptr) {
                user* temp_m = new user(m);
                Pm = temp_m;
                userList.push_back(temp_m);
            }
  
            Pn->adj.push_back(Pm);
            Pm->adj.push_back(Pn);
  
            matrix[n][m] = true;
            matrix[m][n] = true;
        }
  
        void print() {
            int min = BFS(userList[0]);
            int idx = 0;
            //cout << userList[idx]->cur << ' ' << min << endl;
  
            for (int i = 1; i < userList.size(); i++) {
                vector<user*> tempV;
  
                int temp = BFS(tempV[i]);
                cout << tempV[i]->cur << ' ' << temp << endl;
                if (min > temp) {
                    idx = i;
                    min = temp;
                }
                else if (min == temp)
                    if (userList[idx]->cur > userList[i]->cur)
                        idx = i;
            }
            cout << userList[idx]->cur << ' ' << min << endl;
        }
  
        int BFS(user* curV) {
            BFS_Q.push(curV);
            BFS_Q.front()->visited = true;
            int stage = 1;
            user* v = BFS_Q.front();
            while (!BFS_Q.empty()) {
                stage = (v->BFScount == BFS_Q.front()->BFScount) ? stage : stage + 1;
                v = BFS_Q.front();
                BFS_Q.pop();
                for (int i = 0; i < v->adj.size(); i++) {
                    user* temp = v->adj[i];
                    if (!temp->visited) {
                        temp->visited = true;
                        BFS_Q.push(temp);
                        temp->BFScount = stage;
                    }
                    else {
                    }
                }
            }
            int count = 0;
            for (auto iter = userList.begin(); iter != userList.end(); ++iter)
                count += (*iter)->BFScount;
            return count;
        }
    };
  
    int main() {
        int n, m;
        cin >> n >> m;
        graph g;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            g.insert_edge(a, b);
        }
        g.print();
        return 0;
    }

 

---