반응형

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

 

1486번: 등산

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. 지도를 입력받고, arr 배열에 높이를 저장합니다.

 

2. 각 좌표에 번호를 달고 플로이드 와샬 알고리즘을 통해 floyd[ N * M ][ N * M ] 배열에 번호별로 이동거리를 저장합니다.

 

3. floyd[ 0 ][ i ] + floyd[ i ][ 0 ]의 값이 D보다 작은 번호들 중 좌표의 높이값이 가장 큰 값을 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<string>
#include<cmath>
 
using namespace std;
 
int N, M, T, D;
int arr[25][25];
int floyd[625][625];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> T >> D;
 
    for (int i = 0; i < N; i++) {
        string temp;
        cin >> temp;
 
        for (int j = 0; j < M; j++) {
            if (temp[j] >= 'a') {
                arr[i][j] = temp[j] - 'a' + 26;
            }
            else {
                arr[i][j] = temp[j] - 'A';
            }
        }
    }
 
    for (int i = 0; i < N * M; i++) {
        for (int j = 0; j < N * M; j++) {
            floyd[i][j] = -1;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 4; k++) {
                int yy = i + dy[k];
                int xx = j + dx[k];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < M && abs(arr[yy][xx] - arr[i][j]) <= T) {
                    if (arr[i][j] < arr[yy][xx]) {
                        floyd[M * i + j][M * yy + xx] = (arr[yy][xx] - arr[i][j]) * (arr[yy][xx] - arr[i][j]);
                    }
                    else {
                        floyd[M * i + j][M * yy + xx] = 1;
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < N * M; i++) {
        for (int j = 0; j < N * M; j++) {
            for (int k = 0; k < N * M; k++) {
                if (j!=k && floyd[j][i] != -1 && floyd[i][k] != -1) {
                    if (floyd[j][k] == -1 || floyd[j][k] > floyd[j][i] + floyd[i][k]) {
                        floyd[j][k] = floyd[j][i] + floyd[i][k];
                    }
                }
            }
        }
    }
 
    int ans = arr[0][0];
 
    for (int i = 1; i < N * M; i++) {
        if (floyd[0][i] != -1 && floyd[i][0] != -1 && floyd[i][0] + floyd[0][i] <= D) {
            ans = max(ans, arr[i / M][i % M]);
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
반응형

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

 

2610번: 회의준비

첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. 서로 알고 있는 관계에 대해 입력받고, 그래프로 이어줍니다.

 

2. dfs를 활용하여 이어져 있는 사람들끼리 그룹으로 묶고, 번호를 매기고, 각 사람들이 어떤 그룹에 속해있는지 저장합니다.

 

3. 플로이드 와샬 알고리즘을 이용하여 각 사람들끼리의 거리를 저장합니다.

 

4. 1부터 N까지 for문을 이용해 돌면서 각 번호의 사람이 이어져 있는 사람 중 가장 먼 사람을 Max에 저장하고, 그 값이 가장 적은 사람을 ans[ i ]에 저장합니다.

 

[ 소스코드 ]

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> list[101];
int group[101];
int arr[101][101];
pair<int,int> ans[101];
int cnt;
 
void dfs(int cur)
{
    for (auto& next : list[cur]) {
        if (group[next] == 0) {
            group[next] = cnt;
            dfs(next);
        }
    }
 
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        list[u].push_back(v);
        list[v].push_back(u);
        arr[u][v] = 1;
        arr[v][u] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        if (group[i] == 0) {
            group[i] = ++cnt;
            dfs(i);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][i] != 0 && arr[i][k] != 0) {
                    if (arr[j][k] == 0 || arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= cnt; i++) {
        ans[i].second = 987654321;
    }
 
    for (int i = 1; i <= N; i++) {
        int Max = 0;
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                Max = max(Max, arr[i][j]);
            }
        }
 
        if (ans[group[i]].second > Max) {
            ans[group[i]].second = Max;
            ans[group[i]].first = i;
        }
    }
 
    cout << cnt << '\n';
 
    sort(ans + 1, ans + cnt + 1);
 
    for (int i = 1; i <= cnt; i++) {
        cout << ans[i].first << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
반응형

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

 

2224번: 명제 증명

첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. 명제를 입력받고, arr 배열의 0을 A , 51을 'z'로 설정해서 저장합니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 arr 배열을 갱신해 줍니다.

 

3. arr[ i ][ j ] == 1 && i != j 일 때 명제를 출력합니다.

 

[ 소스코드 ]

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<string>
 
using namespace std;
 
int N;
int arr[52][52];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        string a, b;
        cin >> a;
        cin >> b >> b;
 
        if (a[0] <= 'Z') {
            a[0] -= 'A';
        }
        else {
            a[0] -= 'a';
            a[0] += 26;
        }
 
        if (b[0] <= 'Z') {
            b[0] -= 'A';
        }
        else {
            b[0] -= 'a';
            b[0] += 26;
        }
 
        arr[a[0]][b[0]] = 1;
    }
 
    for (int i = 0; i < 52; i++) {
        for (int j = 0; j < 52; j++) {
            for (int k = 0; k < 52; k++) {
                if (arr[j][i] == 1 && arr[i][k] == 1) {
                    arr[j][k] = 1;
                }
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < 52; i++) {
        for (int j = 0; j < 52; j++) {
            if (arr[i][j] == 1 && i != j) {
                ans++;
            }
        }
    }
 
    cout << ans << '\n';
 
    for (int i = 0; i < 52; i++) {
        for (int j = 0; j < 52; j++) {
            if (arr[i][j] == 1 && i != j) {
                if (i < 26) {
                    if (j < 26) {
                        cout << (char)(i + 'A') << " => " << (char)(j + 'A');
                    }
                    else {
                        cout << (char)(i + 'A') << " => " << (char)(j + 'a' - 26);
                    }
                }
                else {
                    if (j < 26) {
                        cout << (char)(i + 'a' - 26) << " => " << (char)(j + 'A');
                    }
                    else {
                        cout << (char)(i + 'a' - 26) << " => " << (char)(j + 'a' - 26);
                    }
                }
                cout << '\n';
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14
[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
반응형

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

 

14588번: Line Friends (Small)

Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. 각각의 선분을 priority_queue에 넣어서 닿아 있다면 arr[ N ][ N ] 배열을 1로 초기화해줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 arr 배열을 갱신해줍니다.

 

3. arr[ i ][ j ]가 0이라면 -1을출력하고 그렇지 않다면 arr[ i ][ j ]를 출력합니다.

 

 

[ 소스코드 ]

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
struct node {
    int num;
    int pos;
    char cur;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (left.pos == right.pos) {
            if (left.cur == 'L') return true;
            else false;
        }
        return left.pos < right.pos;
    }
};
 
int N, Q;
int arr[301][301];
 
int main()
{
    scanf("%d", &N);
 
    priority_queue<node, vector<node>, cmp> pq;
 
    for (int i = 1; i <= N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        pq.push({ i,a,'L' });
        pq.push({ i,b,'R' });
    }
 
    vector<int> stat;
 
    while (!pq.empty()) {
        const int num = pq.top().num;
        const int pos = pq.top().pos;
        const char cur = pq.top().cur;
        pq.pop();
 
        if (cur == 'L') {
            for (int& next : stat) {
                arr[next][num] = 1;
                arr[num][next] = 1;
            }
            stat.push_back(num);
        }
        else {
            for (auto i = stat.begin(); i != stat.end();i++) {
                if (*i == num) {
                    stat.erase(i);
                    break;
                }
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][i] != 0 && arr[i][k] != 0) {
                    if (arr[j][k] == 0) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                    else {
                        arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
                    }
                }
            }
        }
    }
 
    scanf("%d", &Q);
 
    for (int i = 0; i < Q; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (arr[a][b] != 0) {
            printf("%d\n", arr[a][b]);
        }
        else {
            printf("-1\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
반응형

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

 

11562번: 백양로 브레이크

서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. arr[ N ][ N ] 배열을 만들어 양방향 도로라면 1, 아니라면 -1로 초기화합니다.

 

2. 플로이드 와샬 알고리즘을 통해 단방향 도로의 개수를 세서 arr 배열을 갱신해 줍니다.

 

3. arr[ s ][ e ]가 0보다 작다면 -arr[ s ][ e ]를 출력하고, 0보다 크다면 0을 출력합니다.

 

[ 소스코드 ]

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
 
using namespace std;
 
int n, m;
int arr[251][251];
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        arr[i][i] = 1;
    }
 
    for (int i = 0; i < m; i++) {
        int u, v, b;
        scanf("%d %d %d", &u, &v, &b);
 
        if (b == 0) {
            arr[u][v] = 1;
            arr[v][u] = -1;
        }
        else {
            arr[u][v] = arr[v][u] = 1;
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (arr[j][i] != 0 && arr[i][k] != 0) {
                    if (arr[j][i] > 0 && arr[i][k] > 0) {
                        arr[j][k] = 1;
                    }
                    else if (arr[j][i] < 0 && arr[i][k] < 0) {
                        if (arr[j][k] != 0) {
                            arr[j][k] = max(arr[j][k], arr[j][i] + arr[i][k]);
                        }
                        else {
                            arr[j][k] = arr[j][i] + arr[i][k];
                        }
                    }
                    else if (arr[j][i] < 0) {
                        if (arr[j][k] != 0) {
                            arr[j][k] = max(arr[j][k], arr[j][i]);
                        }
                        else {
                            arr[j][k] = arr[j][i];
                        }
                    }
                    else if (arr[i][k] < 0) {
                        if (arr[j][k] != 0) {
                            arr[j][k] = max(arr[j][k], arr[i][k]);
                        }
                        else {
                            arr[j][k] = arr[i][k];
                        }
                    }
                }
            }
        }
    }
 
    int k;
 
    scanf("%d", &k);
 
    for (int i = 0; i < k; i++) {
        int s, e;
        scanf("%d %d", &s, &e);
 
        if (arr[s][e] > 0) {
            printf("0\n");
        }
        else {
            printf("%d\n", -arr[s][e]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11000번 - 강의실 배정 (C++)  (0) 2023.04.22
[ 백준 ] 20311번 - 화학 실험 (C++)  (0) 2023.04.21
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
[ 백준 ] 1507번 - 궁금한 민호 (C++)  (0) 2023.04.17
반응형

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

 

1507번: 궁금한 민호

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

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

 

2. 플로이드 와샬 알고리즘을 이용하여 최단거리가 갱신되면 -1을 출력하고, 해당 노드 간의 거리가 두 간선의 길이의 합과 같다면 두 간선을 ans 배열에 따로 저장해 줍니다.

 

3. 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[21][21];
int ans[21][21];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][k] > arr[j][i] + arr[i][k]) {
                    printf("-1");
                    return 0;
                }
                else if (arr[j][k] == arr[j][i] + arr[i][k]) {
                    if (ans[j][k] != -1 && ans[j][i] != -1 && ans[i][k] != -1) {
                        ans[j][k] = -1;
                        ans[j][i] = arr[j][i];
                        ans[i][k] = arr[i][k];
                    }
                }
            }
        }
    }
 
    int ret = 0;
 
    for (int i = 1; i < N; i++) {
        for (int j = i+1; j <= N; j++) {
            if (ans[i][j] != -1) {
                ret += ans[i][j];
            }
        }
    }
 
    printf("%d", ret);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
[ 백준 ] 2668번 - 숫자고르기 (C++)  (0) 2023.04.16
[ 백준 ] 1253번 - 좋다 (C++)  (0) 2023.04.15
[ 백준 ] 2749번 - 피보나치 수 3 (C++)  (0) 2023.04.14
반응형

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
반응형

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

 

1719번: 택배

첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

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

 

2. ans[ n ][ n ] 배열을 만들어 각 노드까지 갈 때 가장 처음으로 거치는 노드를 저장해 줍니다.

 

3. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 주고, 최단거리를 갱신할 때 ans[ j ][ k ] = ans[ j ][ i ]를 같이 처리해 줍니다.

 

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

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

[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
반응형

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

 

11265번: 끝나지 않는 파티

입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸

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. arr[ A ][ B ]의 값이 C보다 크다면 Stay here을 출력하고 아니라면 Enjoy other party를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[501][501];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    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]);
            }
        }
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
 
        if (arr[A][B] > C) {
            printf("Stay here\n");
        }
        else {
            printf("Enjoy other party\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
반응형

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

 

23286번: 허들 넘기

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

1. arr[ N ][ N ] 배열을 만들어서 값을 987654321로 초기화해 줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 이동 구간 중 가장 높은 허들의 높이가 가장 낮은 값으로 arr 배열을 갱신합니다.

 

3. arr[ u ][ v ]의 값이 987654321이라면 -1을 아니라면 arr[ u ][ v ]를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M, T;
int arr[301][301];
 
int main()
{
    scanf("%d %d %d", &N, &M, &T);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            arr[i][j] = 987654321;
        }
    }
 
    for (int i = 0; i < M; i++) {
        int u, v, h;
        scanf("%d %d %d", &u, &v, &h);
 
        arr[u][v] = h;
    }
 
    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], max(arr[j][i], arr[i][k]));
            }
        }
    }
 
    for (int i = 0; i < T; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        if (arr[u][v] == 987654321) {
            printf("-1\n");
        }
        else {
            printf("%d\n", arr[u][v]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22

+ Recent posts

티스토리툴바