반응형

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

 

1106번: 호텔

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 홍보 비용과 효과를 입력받고, pair<int, int> arr 배열에 저장합니다.

 

2. cus[ i ] 배열을 만들어 i명의 손님을 받았을 때 최소 비용을 저장합니다.

 

3. cus[ j + arr[ i ].second ]  = min(cus[ j + arr[ i ].second ], cus[ j ] + arr[ i ].first) 의 점화식을 통해 배열을 갱신해 줍니다.

 

4. j의 값이 C보다 크거나 같을 때 최솟값을 ans에 저장합니다.

 

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
#include<iostream>
 
using namespace std;
 
int C, N;
pair<int, int> arr[20];
int cus[1111];
int ans = 987654321;
 
int main()
{
    scanf("%d %d", &C, &N);
 
    fill(cus+1, cus + 1111, 987654321);
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < C; j++) {
            cus[j + arr[i].second] = min(cus[j + arr[i].second], cus[j] + arr[i].first);
 
            if (j + arr[i].second >= C) {
                ans = min(ans, cus[j + arr[i].second]);
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
반응형

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

 

1240번: 노드사이의 거리

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연결된 노드와 거리를 입력받고, vector<pair<int, int>> list[ 1001 ]에 저장합니다.

 

2. visited 배열을 만들어 각 노드의 방문 여부를 기록합니다.

 

3. 거리를 알고 싶은 노드를 입력 받고, 깊이 우선 탐색을 활용하여 노드 사이의 거리를 출력합니다.

 

4. visited 배열을 초기화 합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[1001];
int visited[1001];
int a, b;
 
void dfs(int num, int dist)
{
    if (num == b) {
        printf("%d\n", dist);
        return;
    }
    for (auto& next : list[num]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, dist + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    for (int i = 0; i < M; i++) {
        fill(visited, visited + N + 1, 0);
        scanf("%d %d", &a, &b);
        visited[a] = 1;
        dfs(a, 0);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
반응형

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

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 노드의 부모 노드를 입력받고, 부모 노드가 -1일 경우 해당 노드를 root 변수에 저장합니다.

 

2. 입력받은 부모 노드를 기준으로 vector<int> list[ 50 ] 배열에 그래프를 저장합니다.

 

3. dfs를 활용하여 지울 노드들을 방문 처리해 줍니다.

 

4. dfs를 활용하여 루트 노드부터 모든 노드를 방문하면서 자식 노드가 없는 노드들의 개수를 ans에 저장합니다.

 

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[50];
int visited[50];
int ans;
int root;
 
void dfs(int num)
{
    int temp = 0;
    if (visited[num]) return;
    visited[num] = 1;
 
    for (auto& next : list[num]) {
        if (visited[next] != 1) {
            dfs(next);
            temp++;
        }
    }
 
    if (temp == 0) ans++;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        if (num != -1) {
            list[num].push_back(i);
        }
        else {
            root = i;
        }
    }
 
    int del;
    scanf("%d", &del);
 
    dfs(del);
 
    ans = 0;
 
    dfs(root);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
반응형

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

 

27009번: Out of Hay

The cows have run out of hay, a horrible event that must be remedied immediately. Bessie intends to visit the other farms to survey their hay situation. There are N (2 ≤ N ≤ 2,000) farms (numbered 1..N); Bessie starts at Farm 1. She'll traverse some or

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고 arr 배열에 저장합니다.

 

2. 간선의 길이를 기준으로 오름차순으로 arr 배열을 정렬합니다.

 

3. Union-Find를 활용하여 모든 노드를 이어 주고, 그중 가장 긴 간선을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, L;
};
 
bool cmp(node left, node right)
{
    return left.L < right.L;
}
 
int N, M;
int vect[2001];
node arr[10000];
 
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);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].A, &arr[i].B, &arr[i].L);
    }
 
    int ans = 0;
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int L = arr[i].L;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ans = max(ans, L);
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
반응형

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

 

16202번: MST 게임

첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고 arr 배열에 저장합니다.

 

2. 총 K번 for문을 돌면서 MST를 만들고, 그중 가장 짧은 간선을 제거하면서 MST의 길이를 출력해 줍니다.

 

3. 만약 MST를 만들 수 없다면 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
 #include<iostream>
 
using namespace std;
 
int N, M, K;
pair<int, int> arr[10001];
int vect[1001];
int Min = 1;
bool zero = false;
 
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);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= M; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int k = 0; k < K; k++) {
        int ans = 0;
        int temp = 987654321;
        if (zero) {
            printf("0 ");
            continue;
        }
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = Min; i <= M; i++) {
            const int a = arr[i].first;
            const int b = arr[i].second;
 
            if (Find(a) != Find(b)) {
                Union(a, b);
                ans += i;
                temp = min(temp, i);
            }
        }
 
        Min = temp + 1;
 
        for (int i = 2; i <= N; i++) {
            if (Find(1) != Find(i)) {
                printf("0 ");
                zero = true;
                break;
            }
        }
 
        if (zero != true) {
            printf("%d ", ans);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
반응형

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

 

21924번: 도시 건설

첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, ans에 더해줍니다.

 

2. 입력받은 간선을 길이를 기준으로 오름차순으로 정렬합니다.

 

3. for문으로 모든 간선을 탐색하면서 Union-Find를 활용하여 이어주고, ans에서 간선을 빼줍니다.

 

4. for문을 통해 2부터 N번 노드까지 탐색하면서 1번 노드와 부모 노드가 다른 노드가 하나라도 있다면 -1을 출력하고, 그렇지 않다면 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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct node {
    int a;
    int b;
    ll c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N, M;
ll ans;
int vect[100001];
node arr[500000];
 
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);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %lld", &arr[i].a, &arr[i].b, &arr[i].c);
        ans += arr[i].c;
    }
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int a = arr[i].a;
        const int b = arr[i].b;
        const ll c = arr[i].c;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans -= c;
        }
    }
 
    for (int i = 2; i <= N; i++) {
        if (Find(1) != Find(i)) {
            printf("-1");
            return 0;
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
반응형

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

 

13905번: 세부

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받습니다.

 

2. 입력받은 간선을 길이를 기준으로 내림차순으로 정렬합니다.

 

3. for문으로 모든 간선을 탐색하면서 Union-Find를 활용하여 이어줍니다.

 

4. s와 e 노드가 연결되면 연결된 간선 중 가장 짧은 간선의 길이를 출력합니다.

 

5. s와 e 노드가 연결될 수 없다면 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int h1;
    int h2;
    int k;
};
 
bool cmp(node left, node right)
{
    return left.k > right.k;
}
 
int N, M;
int s, e;
node arr[300001];
int vect[100001];
 
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);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
    scanf("%d %d", &s, &e);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].h1, &arr[i].h2, &arr[i].k);
    }
 
    int ans = 987654321;
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int h1 = arr[i].h1;
        const int h2 = arr[i].h2;
        const int k = arr[i].k;
 
        if (Find(h1) != Find(h2)) {
            Union(h1, h2);
            ans = min(ans, k);
        }
 
        if (Find(s) == Find(e)) {
            printf("%d", ans);
            return 0;
        }
    }
 
    printf("0");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
반응형

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

 

5972번: 택배 배송

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra를 활용하여 1부터 N까지 이동합니다.

 

2. 이동거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[50001];
int visited[50001];
 
int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    scanf("%d %d", &N, &M);
 
    fill(visited, visited + N + 1, 987654321);
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
 
        list[A].push_back({ B,C });
        list[B].push_back({ A,C });
    }
 
    pq.push({ 0,1 });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int dist = pq.top().first;
        pq.pop();
 
        if (cur == N) {
            printf("%d", dist);
            return 0;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            const int nNode = next.first;
            const int nDist = next.second;
 
            if (visited[nNode] > dist + nDist) {
                visited[nNode] = dist + nDist;
                pq.push({ visited[nNode], nNode });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
반응형

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

 

14284번: 간선 이어가기 2

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra를 활용하여 s부터 t까지 이동합니다.

 

2. 이동거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int n, m, s, t;
vector<pair<int, int>> list[5001];
int visited[5001];
 
int main()
{
    scanf("%d %d", &n, &m);
 
    fill(visited, visited + n + 1, 987654321);
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    scanf("%d %d", &s, &t);
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
    pq.push({ 0,s });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int dist = pq.top().first;
        pq.pop();
 
        if (cur == t) {
            printf("%d", dist);
            return 0;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            const int nextNode = next.first;
            const int nextDist = next.second;
 
            if (visited[nextNode] > dist + nextDist) {
                visited[nextNode] = dist + nextDist;
                pq.push({ visited[nextNode], nextNode });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13905번 - 세부 (C++)  (0) 2023.03.05
[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
[ 백준 ] 2660번 - 회장뽑기 (C++)  (0) 2023.02.28
반응형

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

 

17396번: 백도어

첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열을 만들어서 적의 시야에 노출되어 있는지 저장합니다.

 

2. dijkstra를 활용하여 적의 시야에 노출되어 있지 않은 간선만을 이용해서 적의 넥서스까지 이동합니다.

 

3. 이동 거리가 int형을 벗어나므로 long long형으로 저장합니다.

 

4. 이동한 거리를 출력하고, 이동이 불가능하다면 -1을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
#define ll long long
 
using namespace std;
 
int N, M;
int arr[100000];
ll visited[100000];
vector<pair<int, ll>> list[100000];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        visited[i] = 11111111111;
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        ll t;
        scanf("%d %d %lld", &a, &b, &t);
        list[a].push_back({ b,t });
        list[b].push_back({ a,t });
    }
 
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
 
    pq.push({ 0,0 });
 
    while (!pq.empty()) {
        const ll dist = pq.top().first;
        const int cur = pq.top().second;
        pq.pop();
 
        if (cur == N - 1) {
            printf("%lld", dist);
            return 0;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            if ((arr[next.first] != 1 && visited[next.first] > dist + next.second) || next.first == N - 1) {
                visited[next.first] = next.second + dist;
                pq.push({ visited[next.first], next.first });
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5972번 - 택배 배송 (C++)  (0) 2023.03.04
[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
[ 백준 ] 2660번 - 회장뽑기 (C++)  (0) 2023.02.28
[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27

+ Recent posts

티스토리툴바