반응형

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

 

14267번: 회사 문화 1

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vector<int> arr[ n ]을 만들고, 직속 후배들을 저장합니다.

 

2. dfs를 활용하여 직속 상사들의 칭찬값들을 모두 더해 후배의 칭찬값에 적용시킵니다.

 

3. 1부터 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<vector>
 
using namespace std;
 
vector<int> arr[100001];
int good[100001];
int ans[100001];
int n, m;
 
void dfs(int num, int w)
{
    if (num == 0) return;
 
    ans[num] = good[num] + w;
 
    for (auto& next : arr[num]) {
        dfs(next, good[num] + w);
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
 
        if (parent != -1) {
            arr[parent].push_back(i);
        }
    }
 
    for (int j = 0; j < m; j++) {
        int i, w;
        scanf("%d %d", &i, &w);
 
        good[i] += w;
    }
 
    dfs(1, 0);
 
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
반응형

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

 

2668번: 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. dfs를 통해서 방문하는 노드마다 경로를 저장하고, 사이클이 생긴다면 해당 지점부터 모든 사이클을 ans 배열에 저장합니다.

 

3. ans 배열의 값이 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
57
58
59
60
61
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
int arr[101];
int visited[101];
int ans[101];
vector<int> box;
int cnt;
 
void dfs(int cur)
{
    if (ans[cur] == 1) return;
 
    if (visited[cur] == 1) {
        bool flag = false;
        for (auto& next : box) {
            if (next == cur) {
                flag = true;
            }
            if (flag == true) {
                ans[next] = 1;
                cnt++;
            }
        }
        box.clear();
        return;
    }
    box.push_back(cur);
 
    visited[cur] = 1;
    dfs(arr[cur]);
    
    return;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= N; i++) {
        if (ans[i] != 1) {
            fill(visited, visited + N + 1, 0);
            dfs(i);
        }
    }
 
    printf("%d\n", cnt);
 
    for (int i = 1; i <= N; i++) {
        if (ans[i] == 1) {
            printf("%d\n", i);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
[ 백준 ] 1507번 - 궁금한 민호 (C++)  (0) 2023.04.17
[ 백준 ] 1253번 - 좋다 (C++)  (0) 2023.04.15
[ 백준 ] 2749번 - 피보나치 수 3 (C++)  (0) 2023.04.14
[ 백준 ] 2436번 - 공약수 (C++)  (0) 2023.04.13
반응형

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 섬을 입력받습니다.

 

2. 2중 for문을 통해 그림을 탐색하면서 1이면 bfs를 통해 이어진 섬을 모두 0으로 바꿔주고, cnt에 1을 더해줍니다.

 

3. cnt를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int arr[50][50];
int dy[8] = { 0,0,-1,1,-1,-1,1,1 };
int dx[8] = { -1,1,0,0,-1,1,1,-1 };
int w, h;
 
void bfs(int y, int x)
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    arr[y][x] = 0;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (yy >= 0 && yy < h && xx >= 0 && xx < w) {
                if (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    while (1) {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) return 0;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        int cnt = 0;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (arr[i][j] == 1) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
 
        printf("%d\n", cnt);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
반응형

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

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그림을 입력받습니다.

 

2. 2중 for문을 통해 그림을 탐색하면서 1이면 bfs를 통해 그림의 크기 중 가장 큰 그림을 ans에 저장하고, cnt++를 해줍니다.

 

3. cnt와 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<queue>
 
using namespace std;
 
int N, M;
int arr[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs(int y, int x)
{
    int ret = 1;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
    arr[y][x] = 0;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                    ret++;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 1) {
                ans = max(ans,bfs(i, j));
                cnt++;
            }
        }
    }
 
    printf("%d\n%d", cnt, ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
반응형

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

 

2617번: 구슬 찾기

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서

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. 2중 for문을 통해 각각의 구슬이 가볍거나 무거운 구슬이 (N + 1) / 2 개보다 많거나 같으면 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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[100][100];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a][b] = 1;
        arr[b][a] = -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] == arr[i][k] && arr[j][i] != 0) {
                    arr[j][k] = arr[j][i];
                }
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        int cnt[2] = { 0 };
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] == 1) {
                cnt[0]++;
            }
            else if (arr[i][j] == -1) {
                cnt[1]++;
            }
        }
        if (cnt[0] >= (N + 1) / 2 || cnt[1] >= (N + 1) / 2) {
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
[ 백준 ] 2660번 - 회장뽑기 (C++)  (0) 2023.02.28
[ 백준 ] 18235번 - 지금 만나러 갑니다 (C++)  (0) 2023.02.26
[ 백준 ] 18405번 - 경쟁적 전염 (C++)  (0) 2023.02.25
[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
반응형

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

 

20010번: 악덕 영주 혜유

FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들어서 arr 배열에 a, b, c를 각각 저장합니다.

 

2. c를 기준으로 arr배열을 오름차순으로 정렬합니다.

 

3. Union-Find를 이용하여 마을들을 연결하고, 열결이 될 때마다 ans에 c를 더해줍니다.

 

4. 또한, 연결이 될 때마다 연결이 된 교역로만으로 그래프를 다시 만듭니다.

 

5. 새로 만든 그래프를 이용하여 한 마을에서 가장 먼 마을을 구하고, 다시 그 마을로부터 가장 먼 마을까지의 거리를 따로 저장합니다.

 

6. 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N, K;
node arr[1000000];
int vect[1000];
vector<pair<int,int>> list[1000];
int visited[1000];
int Max;
int start;
 
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;
}
 
void dfs(int n, int cost)
{
    if (cost > Max) {
        Max = cost;
        start = n;
    }
 
    for (auto& next : list[n]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, cost + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c);
    }
 
    sort(arr, arr + K, cmp);
 
    int ans = 0;
 
    for (int i = 0; i < K; i++) {
        const int a = arr[i].a;
        const int b = arr[i].b;
        const int c = arr[i].c;
 
        if (Find(a) != Find(b)) {
            list[a].push_back({ b,c });
            list[b].push_back({ a,c });
            Union(a, b);
            ans += c;
        }
    }
 
    visited[0] = 1;
    dfs(0, 0);
 
    Max = 0;
    fill(visited, visited + N, 0);
 
    visited[start] = 1;
    dfs(start, 0);
 
    printf("%d\n%d", ans, Max);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
반응형

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

 

1937번: 욕심쟁이 판다

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 대나무 숲을 저장할  arr 배열과, 메모이제이션을 위한 dp 배열을 만듭니다.

 

2. dp[ i ][ j ]에는 i, j 좌표에서 시작했을 때 가장 많이 이동할 수 있는 칸의 수를 저장합니다.

 

3. 따라서, 한번 저장한 좌표에는 다시 갈 필요가 없으므로 dp[ i ][ j ] != 0일 때 dp[ i ][ j ]를 return 합니다.

 

4. 그렇지 않다면 arr[ yy ][ xx ] > arr[ y ][ x ] 일 때, dp[ y ][ x ] = max(dp[ y ][ x ], dfs(yy, xx) + 1)의 점화식을 이용하여 각 좌표의 최댓값을 저장해 줍니다.

 

5. 모든 좌표를 2중 for문을 이용해 돌며 dfs를 실행하고, 그중 최댓값을 ans에 저장합니다.

 

6. 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
#include<iostream>
 
using namespace std;
 
int n;
int arr[500][500];
int dp[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int ans;
 
int dfs(int y, int x)
{
    int& ret = dp[y][x];
    if (ret != 0) return ret;
    ret = 1;
    
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy >= 0 && yy < n && xx >= 0 && xx < n) {
            if (arr[yy][xx] > arr[y][x]) {
                ret = max(ret, dfs(yy, xx) + 1);
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans,dfs(i, j));
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12

+ Recent posts

티스토리툴바