티스토리 뷰

PS/Problem_Solving

[Inflearn] 회장뽑기(DP, 플로이드-워셜, Floyd-Warshall Algorithm)

Aaron 2020. 6. 1. 18:33
반응형


#. Problem

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

* The copyright in this matter is in BOJ


#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램

- 회원 수는 50명을 넘지 않음

- 회원번호는 1부터 회원의 수만큼

- 마지막 줄에는 -1이 두 개 들어있음

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it


#. Solve

플로이드-워셜 알고리즘 응용 문제,


입력이 아래와 같을 때,

5

1 2 

2 3 

3 4 

4 5 

2 4 

5 3 

-1 -1

아래 그림과 같이 그래프를 그릴 수 있다.

 

자기 자신과는 친구가 될 수 없으므로 점수는 0점이 된다.

이제 주어진 인접행렬정보를 dis[][]에 저장해보자.


지금부터가 시작이다.

플로이드-워셜 알고리즘을 적용하여 각 회원들의 점수를 구해보자.


결과를 먼저 보면 아래와 같다.

  

1번 회원의 점수를 보면

1번 회원과 2번 회원과의 거리는 1 (1->2)

1번 회원과 3번 회원과의 거리는 2 (1->2->3)

1번 회원과 4번 회원과의 거리는 2 (1->2->4)

1번 회원과 5번 회원과의 거리는 3 (1->2->4->5)

= 점수의 최댓값인 3이 1번 회원의 점수가 된다.

2번 회원의 점수를 보면

2번 회원과 1번 회원과의 거리는 1 (2->1)

2번 회원과 3번 회원과의 거리는 1 (2->3)

2번 회원과 4번 회원과의 거리는 1 (2->4)

2번 회원과 5번 회원과의 거리는 2 (2->3->5)

= 점수의 최댓값인 2가 2번 회원의 점수가 된다.

...

결과적으로 각 회원의 점수는 아래와 같다.

1번 : 3점

2번 : 2점

3번 : 2점

4번 : 2점

5번 : 3점


Floyd-Warshall 알고리즘의 자세한 동작은 링크를 참고하면 좋을 것 같다.


이제 각 회원의 점수들 중 최솟값이 회장 점수가 되고, 회장 점수를 얻은 회원이 회장 후보가 될 수 있다.


#. Code

ㅇ초기 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100
#define MIN -100
 
int main(void)
{
    int N, a, b, k, i, j, score = MAX, num = 0;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &N);
    vector<vector<int> > dis(N + 1, vector<int>(N + 1, MAX));
    vector<int> cand;
 
    while (true) {
        scanf("%d %d", &a, &b);
        if (a == -1 && b == -1) break;
        dis[a][b] = 1;
        dis[b][a] = 1;
    }
 
    for (i = 1; i <= N; i++)
        dis[i][i] = 0;
 
    for (k = 1; k <= N; k++) {
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (k == i) continue;
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
 
    int maxTemp;
    for (i = 1; i <= N; i++) {
        maxTemp = MIN;
        for (j = 1; j <= N; j++) {
            if (dis[i][j] == 100) {
                dis[i][j] = 0;
                continue;
            }
 
            if (maxTemp < dis[i][j])
                maxTemp = dis[i][j];
        }
 
        if (score > maxTemp) score = maxTemp;
    }
 
    for (i = 1; i <= N; i++) {
        if (*max_element(dis[i].begin()+1, dis[i].end()) == score) {
            num++;
            cand.push_back(i);
        }
    }
 
    printf("%d %d\n", score, num);
    for (i = 0; i < cand.size(); i++)
        printf("%d ", cand[i]);
 
    puts("");
    return 0;
}
cs


ㅇ최적화 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100
#define MIN -100
 
int main(void)
{
    int N, a, b, k, i, j, score = MAX, num = 0;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &N);
    vector<vector<int> > dis(N + 1, vector<int>(N + 1, MAX));
    vector<int> cand(N+1);
 
    while (true) {
        scanf("%d %d", &a, &b);
        if (a == -1 && b == -1) break;
        dis[a][b] = 1;
        dis[b][a] = 1;
    }
 
    for (i = 1; i <= N; i++)
        dis[i][i] = 0;
 
    for (k = 1; k <= N; k++) {
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (k == i) continue;
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
 
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= N; j++) {
            cand[i] = max(cand[i], dis[i][j]);
        }
    }
 
    score = *min_element(cand.begin() + 1, cand.end());
    for (i = 1; i <= N; i++) 
        if (cand[i] == score) 
            num++;
    
    printf("%d %d\n", score, num);
    for (i = 1; i <= N; i++)
        if(cand[i] == score)
            printf("%d ", i);
    puts("");
    return 0;
}
cs


line 16~21) -1이 두 개 입력될 때까지 반복해서 입력을 받음

line 19~20) 친구 사이는 양방향 그래프로 그려짐

line 23~24) 자기 자신은 0점으로 초기화

line 26~33) 여기부터가 플롤이드-워셜 알고리즘의 적용

line 30) 두 정점의 최단 거리를 저장

line 35~39) 각 회원의 점수를 cand[]에 저장

line 41) 회장 점수

line 42~44) 회장 점수와 같은 회장 후보가 몇 명인지

line 47~49) 회장 점수와 같은 회원의 번호를 출력


#. Teach code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int n, a, b, score;
    cin>>n;
    vector<vector<int> > dis(n+1, vector<int>(n+1, 100));
    vector<int> res(n+1);
    for(int i=1; i<=n; i++) dis[i][i]=0;
    while(true){
        cin>>a>>b;
        if(a==-1 && b==-1) break;
        dis[a][b]=1;
        dis[b][a]=1;
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);
            }
        }
    }
    score=100;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) continue;
            res[i]=max(res[i], dis[i][j]);
        }
        score=min(score, res[i]);
    }
    int cnt=0;
    for(int i=1; i<=n; i++){
        if(res[i]==score) cnt++;
    }
    cout<<score<<" "<<cnt<<endl;
    for(int i=1; i<=n; i++){
        if(res[i]==score) cout<<i<<" ";
    }
    return 0;
}
cs



#. Result

  - Input --------------------------------------------------------

5

1 2 

2 3 

3 4 

4 5 

2 4 

5 3 

-1 -1

------------------------------------------------------------------


  - Output --------------------------------------------------------

2 3

2 3 4

------------------------------------------------------------------



반응형
저작자표시

'PS > Problem_Solving' 카테고리의 다른 글

[BOJ] 11055. 14002, 가장 긴 증가하는 부분 수열4 (DP 기초, LIS)  (0) 2020.06.04
[BOJ] 1932.정수삼각형.py.cpp (DP 기초)  (0) 2020.06.03
[Algorithm] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)  (9) 2020.06.01
[Inflearn] 최대점수 구하기(DP, 냅색 알고리즘, knapsack algorithm)  (0) 2020.06.01
[Inflearn] 동전교환(DP, 냅색 알고리즘, knapsack algorithm)  (4) 2020.06.01
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more