반응형

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

 

13424번: 비밀 모임

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

 

1. arr[ N ][ N ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 줍니다.

 

3. 1부터 N까지 K개의 방에서부터 i까지의 거리를 모두 더해주고, 그 값들 중 가장 작은 값을 ans에 저장해 줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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<iostream>
 
using namespace std;
 
int arr[101][101];
int room[101];
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N, M, K;
        scanf("%d %d", &N, &M);
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    arr[i][j] = 0;
                }
                else {
                    arr[i][j] = 987654321;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            arr[a][b] = c;
            arr[b][a] = c;
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
 
        scanf("%d", &K);
        int dist = 987654321;
        int ans = 0;
 
        for (int i = 0; i < K; i++) {
            scanf("%d", &room[i]);
        }
 
        for (int i = 1; i <= N; i++) {
            int temp = 0;
            for (int j = 0; j < K; j++) {
                temp += arr[i][room[j]];
            }
            if (dist > temp) {
                dist = temp;
                ans = i;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30

+ Recent posts

티스토리툴바