반응형

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

 

13023번: ABCDE

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연결된 노드들 끼리 vector<int> list[ N ]을 통해 이어줍니다.

 

2. visited 배열을 만들어 0으로 초기화 시켜주고, dfs를 활용하여 깊이를 구해줍니다.

 

3. 깊이가 5이상이라면 1을 출력하고, 아니라면 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
int ans;
vector<int> list[2000];
int visited[2000];
 
void dfs(int cur, int cnt)
{
    ans = max(ans, cnt);
    if (ans > 4) return;
    cnt++;
 
    for (auto& next : list[cur]) {
        if (visited[next] != 1) {
            visited[next] = 1;
            dfs(next, cnt);
            visited[next] = 0;
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    for (int i = 0; i < N; i++) {
        fill(visited, visited + N, 0);
        visited[i] = 1;
        dfs(i, 1);
    }
 
    if (ans > 4) {
        printf("1");
    }
    else{
        printf("0");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
반응형

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

 

17490번: 일감호에 다리 놓기

2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 노드에서 돌을 놓아야 하는 개수를 입력받아 cost 배열에 저장합니다.

 

2. 끊긴 간선들은 isEdge 배열에 true로 저장합니다.

 

3. 끊긴 간선들을 제외하고 Union-Find를 이용하여 이어줍니다.

 

4. 이어줄 때 이어진 노드들 중 돌을 놓아야 하는 개수가 가장 적은 값으로 cost 배열을 갱신해줍니다.

 

5. 섬의 노드 번호를 0으로 두고, 모든 노드들을 0과 이어주면서 cost가 K를 넘으면 NO를 출력하고, 넘지 않으면 YES를 출력합니다.

 

6. 꼬리를 물고 이어져 있으므로 M의 값이 1보다 작거나 같으면 무조건 YES를 출력해줍니다.

 

[ 소스코드 ]

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<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int N, M;
ll K;
int cost[1000001];
bool isEdge[1000001];
int vect[1000001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    cost[pa] = cost[pb] = min(cost[pa], cost[pb]);
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d %lld", &N, &M, &K);
 
    if (M <= 1) {
        printf("YES");
        return 0;
    }
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        scanf("%d", &cost[i]);
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a != N || b != 1) {
            if (a > b) {
                swap(a, b);
            }
        }
 
        isEdge[a] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!isEdge[i]) {
            if (i == N) {
                Union(1, N);
            }
            else {
                Union(i + 1, i);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (Find(i) != 0) {
            K -= cost[Find(i)];
            Union(0, i);
        }
 
        if (K < 0) {
            printf("NO");
            return 0;
        }
    }
 
    printf("YES");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
반응형

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

 

14921번: 용액 합성하기

홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받습니다.

 

2. start = 0, end = N - 1로 설정하고, arr[ start ] + arr[ end ]의 값이 0보다 크다면 end--를 해주고 0보다 작다면 start++를 해줍니다.

 

3. arr[ start ] + arr[ end ]의 절댓값이 최솟값일 때 ans에 arr[ start ] + arr[ end ]를 저장합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100000];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int start = 0;
    int end = N - 1;
    int ans = 987654321;
 
    while (start < end) {
        int temp = arr[start] + arr[end];
 
        if (temp > 0) {
            end--;
        }
        else if(temp < 0) {
            start++;
        }
        else {
            ans = 0;
            break;
        }
 
        if (abs(ans) > abs(temp)) {
            ans = temp;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
반응형

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/1781

 

1781번: 컵라면

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 데드라인과 컵라면 개수를 입력받고 arr 배열에 저장합니다.

 

2. arr배열을 데드라인을 기준으로 오름차순으로 정렬합니다.

 

3. 1부터 N까지 for문을 통해 돌면서 priority_queue에 넣어주고, arr[ i ]의 데드라인보다 pq.size()가 크면 pq.pop()을 해줍니다.

 

4. pq에 있는 모든 값을 더하고, 출력합니다.

 

[ 소스코드 ]

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<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int ans;
 
int main()
{
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<pair<int, int>> arr;
    
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr.push_back({ a,b });
    }
 
    sort(arr.begin(), arr.end());
 
    for (int i = 0; i < N; i++) {
        pq.push(arr[i].second);
        
        if (arr[i].first < pq.size()) {
            pq.pop();
        }
    }
 
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
반응형

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

 

15989번: 1, 2, 3 더하기 4

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 점화식 arr[ i ] = arr[ i - 3 ] + i / 2 + 1을 통해 arr 배열을 초기화해 줍니다.

 

2. arr[ n ]을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T;
int arr[10001];
 
int main()
{
    scanf("%d", &T);
 
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 3;
 
    for (int i = 4; i <= 10000; i++) {
        arr[i] = arr[i - 3] + i / 2 + 1;
    }
 
    for (int i = 0; i < T; i++) {
        int n;
        scanf("%d", &n);
 
        printf("%d\n", arr[n]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
반응형

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

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

 

15422번: Bumped!

The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), th

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ n ][ used ] 배열을 만들어 비행기 표를 썼을 때와 쓰지 않았을 때 이동 거리를 visited 배열에 저장합니다.

 

2. dijkstra를 활용하여 s부터 t까지 이동하고 이동거리를 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<queue>
#define ll long long
 
using namespace std;
 
struct node {
    int cur;
    ll cost;
    int used;
};
 
struct cmp {
    bool operator()(node right, node left)
    {
        return left.cost < right.cost;
    }
};
 
int n, m, f, s, t;
vector<pair<int, int>> list[50000];
ll visited[50000][2];
 
int main()
{
    scanf("%d %d %d %d %d", &n, &m, &f, &s, &t);
    for (int i = 0; i < n; i++) {
        visited[i][0] = visited[i][1] = 3333333333;
    }
 
    for (int i = 0; i < m; i++) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
 
        list[u].push_back({ v,c });
        list[v].push_back({ u,c });
    }
 
    for (int i = 0; i < f; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        list[u].push_back({ v,0 });
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ s,0,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const ll cost = pq.top().cost;
        const int used = pq.top().used;
        pq.pop();
 
        if (visited[cur][used] < cost) continue;
        visited[cur][used] = cost;
 
        if (cur == t) {
            printf("%lld", cost);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (used == 0 && next.second == 0) {
                if (visited[next.first][1] > cost) {
                    visited[next.first][1] = cost;
                    pq.push({ next.first, cost, 1 });
                }
            }
            else if (next.second != 0) {
                if (visited[next.first][used] > cost + next.second) {
                    visited[next.first][used] = cost + next.second;
                    pq.push({ next.first, visited[next.first][used], used});
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
반응형

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

 

21940번: 가운데에서 만나기

위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

1. arr[ N ][ N ] 배열을 만들어서 i != j가 아닐 때 값을 987654321로 초기화해줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 도시 간의 거리를 저장합니다.

 

3. 1부터 N까지 for문을 통해 돌면서 각 도시별로 arr[ i ][ C[ j ] ] + arr[ C[ j ] ][ i ] 중 최댓값을 저장합니다.

 

4. 최댓값 중 최솟값을 ans에 push 합니다.

 

5. 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M, K;
int arr[201][201];
int C[201];
vector<int> ans;
 
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, T;
        scanf("%d %d %d", &A, &B, &T);
 
        arr[A][B] = T;
    }
 
    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) {
                    arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
    }
    
    scanf("%d", &K);
 
    for (int i = 0; i < K; i++) {
        scanf("%d", &C[i]);
    }
 
    int min = 987654321;
 
    for (int i = 1; i <= N; i++) {
        int Max = 0;
        for (int j = 0; j < K; j++) {
            Max = max(Max, arr[i][C[j]] + arr[C[j]][i]);
        }
        
        if (min > Max) {
            min = Max;
            ans.clear();
            ans.push_back(i);
        }
        else if (min == Max) {
            ans.push_back(i);
        }
    }
 
    for (auto& next : ans) {
        printf("%d ", next);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
반응형

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

 

14567번: 선수과목 (Prerequisite)

3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 선수 과목과 후수 과목으로 이어지는 단방향 그래프를 만들어줍니다.

 

2. 1과 동시에 선수과목이 몇 개 필요한지 cnt[ i ]++를 통해 저장해 주고, cnt[ i ]가 0이면 queue에 넣어줍니다.

 

3. queue를 돌면서 cnt[ i ]가 0이면 계속 queue에 넣어주면서 선수과목이 몇 개 필요한지 ans에 저장합니다.

 

4. 1부터 N까지 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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
int cnt[1001];
int ans[1001];
vector<int> list[1001];
 
int main()
{
    scanf("%d %d", &N, &M);
    queue<int> q;
 
    for (int i = 0; i < M; i++) {
        int A, B;
        scanf("%d %d", &A, &B);
 
        list[A].push_back(B);
        cnt[B]++;
    }
 
    for (int i = 1; i <= N; i++) {
        if (cnt[i] == 0) {
            q.push(i);
            ans[i] = 1;
        }
    }
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            cnt[next]--;
            if (cnt[next] == 0) {
                q.push(next);
                ans[next] += ans[cur] + 1;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19

+ Recent posts

티스토리툴바