반응형

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

 

3184번: 양

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, v와 o의 개수를 세어 ans에 저장해 줍니다.

 

2. 방문하지 않은 좌표들을 방문하면서, bfs를 돌려주고, 각 영역의 양과 늑대의 수를 세어주고, 늑대가 양보다 많다면 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
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
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int R, C;
string arr[250];
int visited[250][250];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
pair<int, int> ans;
 
void bfs(int y, int x)
{
    int v = 0, o = 0;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        if (arr[y][x] == 'v') v++;
        else if (arr[y][x] == 'o') o++;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < R && xx >= 0 && xx < C) {
                if (visited[yy][xx] == 0 && arr[yy][xx] != '#') {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    if (v >= o) {
        ans.first -= o;
    }
    else {
        ans.second -= v;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == 'v') {
                ans.second++;
            }
            else if(arr[i][j] == 'o') {
                ans.first++;
            }
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (visited[i][j] == 0 && arr[i][j] != '#') {
                visited[i][j] = 1;
                bfs(i, j);
            }
        }
    }
 
    cout << ans.first << ' ' << ans.second;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
반응형

 

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

 

3967번: 매직 스타

매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 매직 스타를 입력받고, 채워지지 않은 위치를 pos에 저장합니다.

 

2. 재귀함수를 이용하여 각 자리에 알파벳을 채워주고, 각 줄의 합이 282보다 크다면 return해줍니다.

 

3. 모든 자리가 다 찬다면 그대로 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
string str[5];
char arr[12];
int visited[12];
vector<int> pos;
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
    if (arr[1] + arr[2] + arr[3] + arr[4] > 282) return;
    if (arr[0] + arr[2] + arr[5] + arr[7] > 282) return;
    if (arr[0] + arr[3] + arr[6] + arr[10] > 282) return;
    if (arr[7] + arr[8] + arr[9] + arr[10] > 282) return;
    if (arr[1] + arr[5] + arr[8] + arr[11] > 282) return;
    if (arr[4] + arr[6] + arr[9] + arr[11] > 282) return;
 
    if (level == pos.size()) {
        int cnt = 0;
        flag = true;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                if (str[i][j] != '.') {
                    cout << arr[cnt++];
                }
                else {
                    cout << str[i][j];
                }
            }
            cout << '\n';
        }
        return;
    }
 
    for (int i = 0; i < 12; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            arr[pos[level]] = i + 'A';
            dfs(level + 1);
            visited[i] = 0;
            arr[pos[level]] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 5; i++) {
        cin >> str[i];
    }
 
    int cnt = 0;
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            if (str[i][j] != '.') {
                if (str[i][j] == 'x') {
                    pos.push_back(cnt++);
                }
                else {
                    visited[str[i][j] - 'A'] = 1;
                    arr[cnt++] = str[i][j];
                }
            }
        }
    }
 
    dfs(0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
반응형

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

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, 아직 방문하지 않은 모든 좌표를 돌면서 bfs를 진행해줍니다.

 

2. bfs를 진행하면서 이어져 있는 땅들을 cnt로 바꿔주고, 바다와 만나는 점들을 queue에 넣어줍니다.

 

3. 한번더 bfs를 진행하면서 다른 육지와 이어졌을 때의 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int y, x, d;
};
 
int N;
int arr[100][100];
int visited[100][100];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int cnt;
int ans = 987654321;
 
void bfs(int y, int x)
{
    int v[100][100] = { 0 };
    queue<pair<int, int>> q;
    queue<node> qq;
 
    q.push({ y,x });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        arr[y][x] = cnt;
 
        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 < N) {
                if (arr[yy][xx] == 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (arr[yy][xx] == 0 && v[y][x] != 1) {
                    v[y][x] = 1;
                    qq.push({ y,x,0 });
                }
            }
        }
    }
 
    while (!qq.empty()) {
        const int y = qq.front().y;
        const int x = qq.front().x;
        const int d = qq.front().d;
        qq.pop();
 
        if (d >= ans) return;
 
        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 < N) {
                if (arr[yy][xx] == 0 && v[yy][xx] == 0) {
                    v[yy][xx] = 1;
                    qq.push({ yy,xx,d + 1 });
                }
                else if (arr[yy][xx] != 0 && arr[yy][xx] != cnt) {
                    ans = min(ans, d);
                    return;
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 1 && visited[i][j] == 0) {
                visited[i][j] = 1;
                cnt--;
                bfs(i, j);
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
반응형

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

 

7299번: Food Cubes

The spacemen in the space shuttle are waiting for the next escape window to return to the mother land Earth, where they are expected to fall somewhere in the deep blue waters of the Persian Gulf. Bored of waiting with nothing to do, they decide to play a g

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 좌표를 입력받아 해당 좌표의 값을 arr 배열에 1로 저장하고, visited 배열을 선언하여 방문여부를 체크합니다.

 

2. 모든 좌표를 돌면서 방문하지 않은 좌표에서 bfs를 이용하여 주변에 음식이 있는지 체크하고, 좌표 범위를 벗어나면 ret를 false로 갱신합니다. 

 

3. true일 때 ans++를 해주고, 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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct node {
    int x, y, z;
};
 
int T, M;
int arr[101][101][101];
int visited[101][101][101];
int dx[] = { -1,1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,-1,1 };
 
bool bfs(int x, int y, int z)
{
    bool ret = true;
 
    queue<node> q;
    q.push({ x,y,z });
 
    while (!q.empty()) {
        const int x = q.front().x;
        const int y = q.front().y;
        const int z = q.front().z;
        q.pop();
 
        for (int i = 0; i < 6; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            int zz = z + dz[i];
 
            if (xx >= 1 && xx <= 100 && yy >= 1 && yy <= 100 && zz >= 1 && zz <= 100) {
                if (visited[xx][yy][zz] == 0 && arr[xx][yy][zz] == 0) {
                    visited[xx][yy][zz] = 1;
                    q.push({ xx,yy,zz });
                }
            }
            else {
                ret = false;
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> M;
 
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                for (int k = 1; k <= 100; k++) {
                    visited[i][j][k] = 0;
                    arr[i][j][k] = 0;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            arr[x][y][z] = 1;
        }
 
        int ans = 0;
 
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                for (int k = 1; k <= 100; k++) {
                    if (arr[i][j][k] == 0 && visited[i][j][k] == 0) {
                        visited[i][j][k] = 1;
                        if (bfs(i, j, k)) ans++;
                    }
                }
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
반응형

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

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 문자의 자릿수 값을 저장할 box 배열을 선언합니다.

 

2. 각 단어가 입력될 때마다 각 자릿수의 문자에 10의 n승을 곱해 더해줍니다.

 

3. box 배열을 내림차순으로 정렬하고, box[ 0 ] ~ box[ 9 ] 까지의 값에 9 ~ 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
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
 
using namespace std;
 
int N;
int box[26];
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
 
        for (int j = 0; j < str.size(); j++) {
            box[str[j] - 'A'] += pow(10, str.size() - j - 1);
        }
    }
 
    sort(box, box + 26, greater<>());
 
    int seq = 0;
 
    for (int i = 9; i >= 0; i--) {
        ans += box[seq] * i;
        seq++;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
반응형

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

 

6067번: Guarding the Farm

There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받아 arr 배열에 저장하고, visited 배열을 선언하여 방문여부를 체크합니다.

 

2. 모든 좌표를 돌면서 방문하지 않은 좌표에서 bfs를 이용하여 주변에 더 높은 지형이 있는지 체크하고 더 높은 지형이 없다면 true를 아니라면 false를 return 합니다.

 

3. true일 때 ans++를 해주고, 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[700][700];
int visited[700][700];
int dy[] = { -1,-1,0,1,1,1,0,-1 };
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
 
bool bfs(int y, int x)
{
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    bool ret = true;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (visited[yy][xx] != 1 && arr[yy][xx] == arr[y][x]) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (arr[yy][xx] > arr[y][x]) {
                    ret = false;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] != 1) {
                visited[i][j] = 1;
                if (bfs(i, j)) {
                    ans++;
                }
            }
        }
    }
 
    cout << ans;
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
반응형

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

 

28421번: 곱하기와 쿼리

길이가 $N$인 수열 $A_1, A_2, A_3, \cdots, A_N$이 주어진다. 다음 질의를 수행하는 프로그램을 작성하시오. 1 $x$: 수열에서 서로 다른 두 수 $i$, $j$를 골라 $A_i$, $A_j$를 곱하여 $x$를 만들 수 있으면 $1$, 없

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 저장할 arr[ N ] 배열을 선언합니다.

 

2. 각 수의 개수를 저장할 box[ 10001 ] 배열을 선언합니다.

 

3. 수열을 입력받고, 각 숫자들의 개수를 box 배열에 더해줍니다.

 

4. 쿼리를 입력받을 때마다 1부터 i * i <= x까지 for문을 돌면서 숫자의 존재를 box 배열을 통해 체크하고, 두 수를 곱해서 x를 만들 수 있다면 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
 
using namespace std;
 
int N, Q;
int arr[100001];
int box[20001];
 
bool check(int x)
{
    int i = 1;
 
    if (N == 1) return false;
 
    if (x == 0) {
        if (box[0]) {
            return true;
        }
        else return false;
    }
 
    if (x > 10000) {
        i = x / 10000;
    }
 
    for (i; i * i <= x; i++) {
        if (box[i] && x % i == 0 && box[x / i]) {
            if (i * i == x && box[i] < 2) {
                continue;
            }
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        box[arr[i]]++;
    }
 
    for (int i = 0; i < Q; i++) {
        int cmd, x;
        cin >> cmd >> x;
 
        if (cmd == 1) {
 
            if (check(x)) {
                cout << 1;
            }
            else {
                cout << 0;
            }
 
            cout << '\n';
        }
        else {
            box[0]++;
            box[arr[x]]--;
            arr[x] = 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
반응형

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

 

1939번: 중량제한

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언하고, vect[ i ] = i로 초기화합니다.

 

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
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, C;
};
 
bool cmp(node left, node right)
{
    return left.C > right.C;
}
 
int N, M;
node arr[100000];
int vect[10001];
 
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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        arr[i] = { A,B,C };
    }
 
    int s, e;
    cin >> s >> e;
 
    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 C = arr[i].C;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
        }
 
        if (Find(s) == Find(e)) {
            cout << C;
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25

+ Recent posts

티스토리툴바