반응형

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

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 인접한 노드끼리 같은 집합에 속해있는지 체크합니다.

 

2. dfs를 통해 모든 노드를 탐색하며 인접한 노드끼리 같은 집합에 속해있다면 false를 return 합니다.

 

3. 이분 그래프라면 YES를 출력하고, 그렇지 않다면 NO를 출력합니다.    

 

[ 소스코드 ]

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<vector>
 
using namespace std;
 
int K, V, E;
vector<int> list[20001];
int visited[20001];
 
bool dfs(int cur, int stat)
{
    for (auto& next : list[cur]) {
        if (visited[next] == 0) {
            visited[next] = -stat;
            dfs(next, -stat);
        }
        else if (visited[next] == stat) {
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> K;
 
    while (K--) {
        cin >> V >> E;
        bool flag = true;
 
        for (int i = 1; i <= V; i++) {
            list[i].clear();
            visited[i] = 0;
        }
 
        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            list[u].push_back(v);
            list[v].push_back(u);
        }
 
        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0) visited[i] = 1;
            if (!dfs(i, visited[i])) {
                printf("NO\n");
                flag = false;
                break;
            }
        }
 
        if (flag) {
            printf("YES\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1863번 - 스카이라인 쉬운거 (C++)  (0) 2023.06.29
[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
반응형

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

 

2310번: 어드벤처 게임

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ n ][ 501 ] 배열을 만들어 얼마의 소지금을 들고 해당 노드를 방문했는지 기록합니다.

 

2. vector<int> list[1001]을 이용하여 해당 노드에서 갈 수 있는 노드들을 저장합니다.

 

3. bfs를 활용하여 queue에 넣어가면서 방을 이동하고, n번 방에 도착할 수 있으면 Yes를 출력하고, 그렇지 않으면 No를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int n;
char room[1001];
int charge[1001];
vector<int> list[1001];
int visited[1001][501];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    list[0].push_back(1);
 
    while (1) {
        cin >> n;
        if (n == 0) return 0;
 
        for (int i = 1; i <= n; i++) {
            list[i].clear();
            fill(visited[i], visited[i] + 501, 0);
            cin >> room[i] >> charge[i];
            int next;
            while (1) {
                cin >> next;
                if (next == 0) break;
                list[i].push_back(next);
            }
        }
 
        queue<pair<int, int>> q;
 
        q.push({ 0, 0 });
 
        bool flag = false;
 
        while (!q.empty()) {
            const int cur = q.front().first;
            const int cost = q.front().second;
            q.pop();
 
            if (cur == n) {
                cout << "Yes\n";
                flag = true;
                break;
            }
 
            for (int& next : list[cur]) {
                if (room[next] == 'T') {
                    if (cost >= charge[next]) {
                        if (visited[next][cost] != 1) {
                            visited[next][cost] = 1;
                            q.push({ next,cost - charge[next] });
                        }
                    }
                }
                else if (room[next] == 'L') {
                    if (cost < charge[next]) {
                        if (visited[next][charge[next]] != 1) {
                            visited[next][charge[next]] = 1;
                            q.push({ next,charge[next] });
                        }
                    }
                    else {
                        if (visited[next][cost] != 1) {
                            visited[next][cost] = 1;
                            q.push({ next,cost });
                        }
                    }
                }
                else {
                    if (visited[next][cost] != 1) {
                        visited[next][cost] = 1;
                        q.push({ next,cost });
                    }
                }
            }
        }
 
        if (flag == false) {
            cout << "No\n";
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
반응형

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

+ Recent posts

티스토리툴바