Skip to content

Commit 9fada69

Browse files
Joseph-ChaJoseph-Cha
committed
102번 회장 뽑기 수강 완료
1 parent dcaa29e commit 9fada69

2 files changed

Lines changed: 59 additions & 0 deletions

File tree

인프런_알고리즘_강의/김태원/섹션 5. Dynamic programming(동적계획법)/101.플로이드 워샬 알고리즘.md renamed to 인프런_알고리즘_강의/김태원/섹션 5. Dynamic programming(동적계획법)/101. 플로이드 워샬 알고리즘.md

File renamed without changes.

인프런_알고리즘_강의/김태원/섹션 5. Dynamic programming(동적계획법)/102 회장뽑기(플로이드-워샬 응용).md renamed to 인프런_알고리즘_강의/김태원/섹션 5. Dynamic programming(동적계획법)/102. 회장뽑기(플로이드-워샬 응용).md

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,5 +38,64 @@
3838

3939
### 모범 답안
4040
``` Cpp
41+
#include <iostream>
42+
#include <fstream>
43+
#include <vector>
44+
#include <algorithm>
45+
using namespace std;
46+
int main() {
47+
ios_base::sync_with_stdio(false);
48+
ifstream cin;
49+
cin.open("input.txt");
4150

51+
int n = 0, a = 0, b = 0, score = 100;
52+
cin >> n;
53+
vector<vector<int>> dis(n + 1, vector<int>(n + 1, 100));
54+
vector<int> res(n + 1);
55+
56+
for (int i = 1; i <= n; i++) dis[i][i] = 0;
57+
58+
while (true) {
59+
cin >> a >> b;
60+
if (a == -1 && b == -1) break;
61+
// 양방향 그래프
62+
dis[a][b] = 1;
63+
dis[b][a] = 1;
64+
}
65+
66+
// k가 1일 때 -> 1번 정점에서 각 정점으로 가는 최단 거리
67+
// k가 2일 때 -> 2번 정점에서 각 정점으로 가는 최단 거리
68+
for (int k = 1; k <= n; k++) {
69+
for (int i = 1; i <= n; i++) {
70+
for (int j = 1; j <= n; j++) {
71+
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
72+
}
73+
}
74+
}
75+
76+
for (int i = 1; i <= n; i++) {
77+
for (int j = 1; j <= n; j++) {
78+
res[i] = max(res[i], dis[i][j]);
79+
}
80+
score = min(score, res[i]);
81+
}
82+
83+
int cnt = 0;
84+
for (int i = 1; i <= n; i++) {
85+
if (res[i] == score) cnt++;
86+
}
87+
88+
cout << score << " " << cnt << endl;
89+
90+
for (int i = 1; i <= n; i++) {
91+
if (res[i] == score) {
92+
cout << i << " ";
93+
}
94+
}
95+
96+
return 0;
97+
}
98+
99+
// dis[i][j]의 의미
100+
// i와 j 회원 간 가까운 정도
42101
```

0 commit comments

Comments
 (0)