문제 출처

1. 문제설명

  • 요약해서 설명하겠다.
  • 어떤 그래프가 주어지는데, 모든 정점을 연결하는 최대 깊이를 구하는 문제
  • 예시
    • 인접행렬 : 1->2, 2->3, 2->4, 2->5
    • 모든 점을 잇는데, 깊이가 2가 필요하므로, 답은 2가 된다.


2. 알고리즘 설계

  • 처음에 DFS로 구현했는데 문제를 읽어보기만 해도, 뻗어나가는 BFS가 적합함을 알 수 있다.
  • 우선, 모든 정점에 대한 깊이를 BFS로 구한다.
  • 그리고 깊이를 벡터에 쌓는다.
  • 비어있지 않은 최초의 깊이 벡터가 회장 후보가 된다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

const int SZ = 55;
bool adj[SZ][SZ], vis[SZ];
vector<int> pres[50];
int n, a, b;

int bfs(int s) {
    int ret = 0;
    queue<pii> q;
    q.push({s, 0});
    vis[s] = true;

    while(!q.empty()) {
        pii cur = q.front();
        q.pop();

        ret = max(ret, cur.second);

        for(int i=1; i<=n; i++) {
            if(vis[i] || !adj[cur.first][i]) continue;
            vis[i] = true;
            q.push({i, cur.second+1});
        }
    }

    return ret;
}

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

    cin >> n;
    while (true) {
        cin >> a >> b;
        if (a == -1 && b == -1) break;
        adj[a][b] = adj[b][a] = true;
    }

    for (int i = 1; i <= n; i++) {
        fill_n(&vis[0], SZ, false);
        int cur = bfs(i);
        pres[cur].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        if (pres[i].empty()) continue;

        cout << i << ' ' << pres[i].size() << '\n';
        for (int x : pres[i]) cout << x << ' ';

        break;
    }

    return 0;
}