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

 

2660번: 회장뽑기

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

www.acmicpc.net

플로이드 와샬 알고리즘을 사용해서 3중포문으로 dp table을 생성한뒤에

문제 조건만 잘 따져가면 쉽게 풀 수 있습니다.

 

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
 
#define MAX_N 51
#define INF 1e9
int dp[MAX_N][MAX_N];
 
int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N,a,b; cin >> N;
     for (int i = 1; i <= N; i++) {
          for (int j = 1; j <= N; j++) {
               if (i == j) dp[i][j] = 0;
               else dp[i][j] = INF;
          }
     }
     while (cin >> a >> b) {
          if (a == -1 && b == -1) break;
          dp[a][b] = 1;
          dp[b][a] = 1;
     }
 
     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp[s][m] != INF && dp[m][e] != INF) {
                         dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e]);
                    }
               }
          }
     }
     vector<int> ans;
     int mmin = 1e9;
     for (int i = 1; i <= N; i++) {
          int tmp_max = -1;
          for (int j = 1; j <= N; j++) {
               tmp_max = max(tmp_max, dp[i][j]);
          }
          if (mmin == 1e9) {
               mmin = tmp_max;
               ans.push_back(i);
          }
          else {
               if (mmin < tmp_max) continue;
               else if (mmin == tmp_max) ans.push_back(i);
               else {
                    ans.clear();
                    mmin = tmp_max;
                    ans.push_back(i);
               }
          }
     }
     cout << mmin << " " << ans.size() << "\n";
     for (const auto & x : ans) {
          cout << x << " ";
     }
     cout << "\n";
}

 

 

저작자표시

'알고리즘 > [C++]BOJ' 카테고리의 다른 글

[백준BOJ] 1507 궁금한 민호  (0) 2019.10.06
[백준BOJ] 9205 맥주 마시면서 걸어가기  (0) 2019.10.06
[백준BOJ] 10159 저울  (0) 2019.10.05

+ Recent posts

티스토리툴바