[BOJ] 2660번 회장 선출

복기

처음에 플루이드-와샬 알고리즘을 써야 한다는 것이 떠오르지 않았다. 나중에 생각나서 적용했는데, 그 뒤 회장의 점수와 횟수를 구하는데 너무 복잡하게 풀었다. 단순 명료하게, 오버 엔지니어링 하지 않도록 주의하자.

코드

• C++ 17

#include <iostream> #include <algorithm>   using namespace std;   int N; int Costs[50][50]; int Scores[50];   int main() {   ios::sync_with_stdio(false);   cin.tie(nullptr);   cout.tie(nullptr);     cin >> N;   while (true)   {     int a, b;     cin >> a >> b;       if (a == -1 && b == -1)       break;       Costs[a][b] = 1;     Costs[b][a] = 1;   }     for (int via = 1; via <= N; ++via)   {     for (int s = 1; s <= N; ++s)     {       for (int e = 1; e <= N; ++e)       {         if (Costs[s][via] == 0 || Costs[via][e] == 0 || s == e)           continue;           if (Costs[s][e] == 0 || Costs[s][e] > Costs[s][via] + Costs[via][e])           Costs[s][e] = Costs[s][via] + Costs[via][e];       }     }   }     int minScore = 987654321;   for (int s = 1; s <= N; s++)   {     int m = 0;     for (int e = 1; e <= N; e++)     {       m = max(m, Costs[s][e]);     }     Scores[s] = m;     minScore = min(minScore, m);   }     int presidentNumber = 0;   for (int i = 1; i <= N; i++)   {     if (minScore == Scores[i])       ++presidentNumber;   }      cout << minScore << ' ' << presidentNumber << '\n';   for (int i = 1; i <= N; i++)   {     if (minScore == Scores[i])       cout << i << ' ';   } }

• C# 6.0

using System; using System.Collections.Generic; using System.Text;   namespace Csharp {     class Program     {         static int N;         static int[,] Costs = new int[50, 50];         static int[] Scores = new int[50];           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             while (true)             {                 int a, b;                 var inputs = Console.ReadLine().Split();                 a = Convert.ToInt32(inputs[0]);                 b = Convert.ToInt32(inputs[1]);                   if (a == -1 && b == -1)                     break;                   Costs[a, b] = 1;                 Costs[b, a] = 1;             }               for (int via = 1; via <= N; ++via)             {                 for (int s = 1; s <= N; ++s)                 {                     for (int e = 1; e <= N; ++e)                     {                         if (Costs[s, via] == 0 || Costs[via, e] == 0 || s == e)                             continue;                           if (Costs[s, e] == 0 || Costs[s, e] > Costs[s, via] + Costs[via, e])                             Costs[s, e] = Costs[s, via] + Costs[via, e];                     }                 }             }               int minScore = 987654321;             for (int s = 1; s <= N; ++s)             {                 int m = 0;                 for (int e = 1; e <= N; ++e)                 {                     m = Math.Max(m, Costs[s, e]);                 }                 Scores[s] = m;                 minScore = Math.Min(minScore, m);             }               int presidentNumber = 0;             for (int i = 1; i <= N; ++i)             {                 if (Scores[i] == minScore)                     ++presidentNumber;             }               Console.WriteLine($"{minScore} {presidentNumber}");             for (int i = 1; i <= N; ++i)             {                 if (Scores[i] == minScore)                     Console.Write($"{i} ");             }         }     } }

• Python 3

from sys import stdin input = stdin.readline   N = int(input()) Costs = [ [0] * (N + 1) for _ in range(N + 1) ] Scores = [999999] * (N + 1)   while True:     s, e = map(int, input().split())     if s == -1 and e == -1:         break       Costs[s][e], Costs[e][s] = 1, 1   for via in range(1, N + 1):     for s in range(1, N + 1):         for e in range(1, N + 1):             if Costs[s][via] == 0 or Costs[via][e] == 0 or s == e:                 continue               if Costs[s][e] == 0 or Costs[s][e] > Costs[s][via] + Costs[via][e]:                 Costs[s][e] = Costs[s][via] + Costs[via][e]   for i in range(1, N + 1):     Scores[i] = max(Costs[i]) r = min(Scores)   print(r, Scores.count(r), sep = ' ') for i in range(1, N + 1):     if Scores[i] == r:         print(i, end = ' ')