[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 = ' ') |