[백준] 1389번

알고리즘 및 자료구조 복습이 되는 문제들이여서 좋았다.

floyd이거 까먹고 있었는데 상기 되는 계기가 되었다

O(n*n*m)

m은 bfs의 갯수다, 즉 노드의 갯수 근데 모든 연결점과 연결 되어 있기 때문에, 결론의 O(n^3)일 것이다.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>


int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector graph(n, std::vector<int>(n, 0));
    std::vector<int> visited(n, -1);
    std::queue<int> q;

    for (int i = 0; i<m; i++) {
        int _x, _y;
        std::cin >> _x >> _y;
        graph[_x-1][_y-1] = 1;
        graph[_y-1][_x-1] = 1;
    }

    int distance = INT_MAX;
    int index = 0;
    for (int i = 0; i<n; i++) {
        std::vector<int> _visited = visited;
        q.push(i);
        _visited[i] = 0;
        int _dist = 0;
        while (!q.empty()) {
            int _index = q.front(); q.pop();
            _dist += _visited[_index];
            for (int j = 0; j < n; j++) {
                if (graph[_index][j] && _visited[j] == -1) {
                    _visited[j] = _visited[_index]+1;
                    q.push(j);
                }
            }
        }

        if (distance > _dist) {
            distance = _dist;
            index = i+1;
        }
    }

    std::cout << index << std::endl;

    return 0;
}