[백준/C++] 알고리즘 2660번 - 회장뽑기

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 를 풀어보도록 하겠습니다.

 

https://www.acmicpc.net/problem/2660

 

 

[문제 접근]

처음에 문제를 읽고 머릿속에 명확히 문제 상황이 그려지지 않았습니다.

그래서 예제를 토대로 그림을 그려가며 이해를 시도했습니다. 

사람을 정점으로, 친구관계를 간선으로 치환하여 생각했고,

조건에서 몇 사람을 통하면 모두가 서로 알 수 있다고 했기 때문에 BFS를 이용해서 거리가 가장 먼 정점을 점수로 두었습니다.

인접리스트를 활용하여 BFS를 둘 경우에는 O(V+E)의 시간복잡도가 걸립니다.

제한시간은 1초이지만, 회원의 수가 50명이하여서, O(V+E) * 50 충분히 제한시간 안에  들어갈 수 있다고 판단하였습니다.

 

[풀이 전략]

1. 무방향 그래프임을 감안한 인접리스트를 구현

2. score 배열 선언 

2.BFS 구현

- 방문여부랑 거리를 포함하는 dis 배열 선언 및 초기화

- 한 정점의 BFS 로직이 끝나면 dis 배열에서 가장 큰 값을 그 정점의 score로 설정.

3. 모든 정점에 대해 2번 반복.

 

[코드]

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


vector<int> adj[51];
int score[51] ;


int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    int n ; 
    cin >> n ;

    while (true)
    {
        int a,b ;       
        cin >> a >> b ;
        if(a == -1 && b == -1) break;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    fill(score+1,score+n+1,0);

    for(int i = 1 ; i <= n ; i++) {
        queue<int> q ;
        int dis[n+1] ; 
        fill(dis+1,dis+n+1, -1);
        q.push(i);
        dis[i] = 0;
        while (!q.empty())
        {
            auto cur = q.front(); q.pop();

            for(auto e: adj[cur]) {
                if(dis[e] >= 0) continue;
                dis[e] = dis[cur] + 1;
                q.push(e);
            }
        }
        score[i] = *max_element(dis+1,dis+n+1);
    }

     int min = *min_element(score+1,score+n+1);
      vector<int> result ;
     for(int i = 1 ; i <= n ; i++) {
        if(score[i] == min) result.push_back(i);
     }
    cout << min << ' '<< result.size() <<'\n';
    
    for(auto e : result) cout << e << ' ';
}

 

[배울 점]

- 거리와 방문여부를 나타내는 dis를 처음에 초기화할 때 -1로 할지 혹은 0으로 할지에 대해서 충분히 고민해야 합니다. 만약 처음에 방문한 지점의 dis값을 0으로 설정했는데 dis 초기화값이 0으로 되어 있으면 이 처음 방문 지점은 방문체크가 되지 않습니다.