반응형

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

 

15971번: 두 로봇

입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 방문을 기록해 줍니다.

 

2. 그래프를 입력받고, bfs를 이용하여 시작점부터 끝점까지 이동 거리를 구해줍니다.

 

3. 위의 과정에서 지나갔던 통로 중 가장 긴 통로를 이동 거리에서 빼줍니다.

 

4. 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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int cur;
    int cost;
    int max;
};
 
int N, s, e;
vector<pair<int, int>> list[100001];
int visited[100001];
 
int main()
{
    scanf("%d %d %d", &N, &s, &e);
 
    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 });
    }
 
    queue<node> q;
    q.push({ s,0,0 });
    visited[s] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int cost = q.front().cost;
        const int Max = q.front().max;
        q.pop();
 
        if (cur == e) {
            printf("%d", cost - Max);
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (visited[next.first] != 1) {
                visited[next.first] = 1;
                q.push({ next.first, cost + next.second, max(Max, next.second) });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
반응형

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

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ 501 ][ 501 ] 배열을 만들어서 -1로 초기화합니다.

 

2. dfs를 통해 해당 좌표에 방문 시 visited배열이 -1이 아니라면 그 값을  return 합니다.

 

3. visited 배열을 0으로 초기화시키고, 지도에 적힌 문자대로 이동합니다.

 

4. 이동했을 때 지도 밖으로 나간다면 1을 return 하고, 그렇지 않다면 다시 재귀해 줍니다.

 

5. visited 배열에서 값이 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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int N, M;
char arr[501][501];
int visited[505][505];
 
int dfs(int r, int c)
{
    if (visited[r][c] != -1) return visited[r][c];
    visited[r][c] = 0;
 
    if (arr[r][c] == 'U') {
        if (r == 0) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r - 1, c);
    }
    else if (arr[r][c] == 'R') {
        if (c == M-1) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r, c + 1);
    }
    else if (arr[r][c] == 'D') {
        if (r == N - 1) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r + 1, c);
    }
    else {
        if (c == 0) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r, c - 1);
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
    memset(visited, -1, sizeof(visited));
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] == -1) {
                if (dfs(i, j)) ans++;
            }
            else if (visited[i][j] == 1) ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
반응형

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

 

14466번: 소가 길을 건너간 이유 6

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. road[ r + r` ][ c + c` ] 배열을 만들어 길의 위치를 저장합니다.

 

2. cow 배열을 만들어 소들의 위치를 저장합니다.

 

3. for문을 통해 cow 배열을 돌면서 bfs를 이용하여 몇마리의 소를 만날 수 있는지 ans에 저장합니다.

 

4. ans는 만날 수 있는 모든 경우이므로 겹치는 경우를 빼기 위해 2로 나눈 후, 나올 수 있는 모든 쌍에서 ans/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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, K, R;
int road[205][205];
int arr[101][101];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
vector<pair<int, int>> cow;
 
int bfs(int num)
{
    int ret = 0;
    int visited[101][101] = { 0 };
    queue<pair<int, int>> q;
    q.push({ cow[num].first, cow[num].second });
 
    while (!q.empty()) {
        const int r = q.front().first;
        const int c = q.front().second;
        q.pop();
 
        if (visited[r][c] == 1) continue;
        visited[r][c] = 1;
 
        if (arr[r][c] == 1) {
            ret++;
        }
 
        for (int i = 0; i < 4; i++) {
            const int rr = r + dr[i];
            const int cc = c + dc[i];
 
            if (rr > 0 && rr <= N && cc > 0 && cc <= N) {
                if (road[r + rr][c + cc] != 1) {
                    q.push({ rr,cc });
                }
            }
        }
    }
 
    return ret - 1;
}
 
int main()
{
    scanf("%d %d %d", &N, &K, &R);
 
    for (int i = 0; i < R; i++) {
        int r, c, rr, cc;
        scanf("%d %d %d %d", &r, &c, &rr, &cc);
 
        road[r + rr][c + cc] = 1;    //길의 위치
    }
 
    for (int i = 0; i < K; i++) {
        int r, c;
        scanf("%d %d", &r, &c);
 
        arr[r][c] = 1;
        cow.emplace_back(r, c);
    }
 
    int pair = (K) * (K - 1) / 2;    //나올 수 있는 모든 쌍
 
    int ans = 0;    //길 없이 만날 수 있는 모든 쌍의 수
 
    for (int i = 0; i < cow.size(); i++) {
        ans += bfs(i);
    }
 
    printf("%d", pair - ans / 2);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04
[ 백준 ] 10159번 - 저울 (C++)  (0) 2022.12.03
[ 백준 ] 1039번 - 교환 (C++)  (0) 2022.12.01
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
반응형

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

 

3584번: 가장 가까운 공통 조상

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽어 보고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/95

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까지

rudalsd.tistory.com

 

1. 입력받은 트리를 통해서 루트를 level 1, 이후 자식으로 넘어갈 때마다 level을 1씩 늘려나가면서 각 노드의 level을 저장합니다.

 

2. arr[ N ][ i ]에서 N은 노드의 번호, i는 $2^{i}$번 째 부모를 나타냅니다.

 

3. 입력받은 두 수의 level을 맞춰줍니다.

 

4. 만약 두 수가 같지 않다면 두 수가 같을 때까지 level을 낮춰줍니다.

 

5. 마지막에 그 수를 출력합니다.

 

[ 소스코드 ]

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
103
104
105
106
107
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
 
using namespace std;
 
int N;
int arr[10001][14];
int level[10001];
vector<int> list[10001];
 
void dfs(int num, int lv) {
    level[num] = lv;
    for (auto next : list[num]) {
        dfs(next, lv + 1);
    }
}
 
int find(int A, int B) {
    int ret = 0;
 
    if (level[A] > level[B]) {
        int temp = A;
        A = B;
        B = temp;
    }
 
    int size = ceil(log2(N));
 
    if (level[A] != level[B]) {
        for (int i = size - 1; i >= 0; i--) {
            int next = arr[B][i];
            if (next == 0) continue;
            if (level[A] < level[next]) {
                B = next;
            }
        }
 
        B = arr[B][0];
    }
    
    if (A != B) {
        for (int i = size - 1; i >= 0; i--) {
            int pa = arr[A][i];
            int pb = arr[B][i];
 
            if (pa != pb) {
                A = pa;
                B = pb;
            }
        }
 
        A = arr[A][0];
    }
 
    return A;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d", &N);
 
        int size = ceil(log2(N));
        
        memset(arr, 0, sizeof(arr));
        
        for (int i = 1; i <= N; i++) {
            list[i].clear();
        }
 
        for (int i = 0; i < N - 1; i++) {
            int A, B;
            scanf("%d %d", &A, &B);
 
            arr[B][0] = A;
            list[A].push_back(B);
        }
 
        int root = 0;
 
        for (int i = 1; i <= N; i++) {
            if (arr[i][0] == 0) {
                root = i;
                break;
            }
        }
 
        dfs(root, 1);
 
        for (int i = 1; i < size; i++) {    //희소 배열
            for (int j = 1; j <= N; j++) {
                int next = arr[j][i - 1];
                arr[j][i] = arr[next][i - 1];
            }
        }
 
        int A, B;
        scanf("%d %d", &A, &B);
 
        printf("%d\n", find(A, B));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
[ 백준 ] 5529번 - 저택 (C++)  (0) 2022.11.17
[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
반응형

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

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 섬에 번호를 매기고 각 번호마다 섬의 좌표를 vector에 저장합니다.

 

2. 모든 섬을 2중 for문을 사용하여 서로 간의 최소 거리를 list vector에 저장합니다.

 

3. pq에 출발점, 도착점과 거리를 넣습니다.

 

4. pq에서 하나씩 뽑아서 크루스칼 알고리즘을 통해  MST를 찾아줍니다.

 

5. 모든 섬을 2중 for문을 사용하여 루트 노드가 다른 섬이 하나라도 있다면 -1을 출력해줍니다.

 

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[10][10];
int visited[10][10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<pair<int, int>> pos[7];
vector<pair<int, int>> list[7];
int vect[7];
 
struct node {    
    int start;
    int end;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
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 getDist(int a, int b) //두 섬 사이의 최단 거리 구하기
{
    int ret = 987654321;
 
    for (auto A : pos[a]) {
        for (auto B : pos[b]) {
            if (A.first == B.first) {
                bool flag = false;
                if (A.second > B.second) {
                    for (int i = B.second + 1; i < A.second; i++) {
                        if (arr[A.first][i] == 1) {
                            flag = true;
                            break;
                        }
                    }
                    if (flag == false) {
                        if (A.second - B.second - 1 != 1) {
                            ret = min(ret, A.second - B.second - 1);
                        }
                    }
                }
                else {
                    for (int i = A.second + 1; i < B.second; i++) {
                        if (arr[A.first][i] == 1) {
                            flag = true;
                            break;
                        }
                    }
                    if (flag == false) {
                        if (B.second - A.second - 1 != 1) {
                            ret = min(ret, B.second - A.second - 1);
                        }
                    }
                }
            }
            if (A.second == B.second) {
                bool flag = false;
                if (A.first > B.first) {
                    for (int i = B.first + 1; i < A.first; i++) {
                        if (arr[i][A.second] == 1) {
                            flag = true;
                            break;
                        }
                    }
                    if (flag == false) {
                        if (A.first - B.first - 1 != 1) {
                            ret = min(ret, A.first - B.first - 1);
                        }
                    }
                }
                else {
                    for (int i = A.first + 1; i < B.first; i++) {
                        if (arr[i][A.second] == 1) {
                            flag = true;
                            break;
                        }
                    }
                    if (flag == false) {
                        if (B.first - A.first - 1 != 1) {
                            ret = min(ret, B.first - A.first - 1);
                        }
                    }
                }
            }
        }
    }
 
    if (ret != 987654321) {
        list[a].push_back({ b,ret });
    }
}
 
void bfs(int y, int x, int cnt)    //이어져 있는 땅 찾기
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    visited[y][x] = 1;
    pos[cnt].push_back({ y,x });
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        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 < M) {
                if (visited[yy][xx] != 1 && arr[yy][xx] == 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                    pos[cnt].push_back({ yy,xx });
                }
            }
        }
    }
}
 
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 cnt = 1;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 1 && visited[i][j] != 1) {
                bfs(i, j, cnt);
                cnt++;
            }
        }
    }
 
    cnt;
 
    for (int i = 1; i < cnt; i++) {
        vect[i] = i;
        for (int j = 1; j < cnt; j++) {
            if (i != j) {
                getDist(i, j);
            }
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    for (int i = 1; i < cnt; i++) {
        for (auto next : list[i]) {
            pq.push({ i,next.first,next.second });
        }
    }
 
    int ans = 0;
 
    while (!pq.empty()) {
        int start = pq.top().start;
        int end = pq.top().end;
        int dist = pq.top().dist;
        pq.pop();
 
        if (find(start) != find(end)) {
            Union(start, end);
            ans += dist;
        }
    }
 
    for (int i = 1; i < cnt; i++) {
        for (int j = 1; j < cnt; j++) {
            if (i != j) {
                if (find(i) != find(j)) {
                    printf("%d", -1);
                    return 0;
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15486번 - 퇴사 2 (C++)  (0) 2022.10.14
[ 백준 ] 14442번 - 벽 부수고 이동하기 2 (C++)  (0) 2022.10.13
[ 백준 ] 1956번 - 운동 (C++)  (0) 2022.10.11
[ 백준 ] 23291번 - 어항 정리 (C++)  (0) 2022.10.10
[ 백준 ] 5014번 - 스타트링크 (C++)  (0) 2022.10.09
반응형

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

 

23290번: 마법사 상어와 복제

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. fish struct를 만들어 vector <fish> vect에 물고기의 좌표와 방향을 저장하고, cnt 배열에 물고기의 개수를 저장합니다.

 

2. temp 배열에 물고기의 현재 위치를 저장하고, 물고기를 이동시키고, cnt 배열을 갱신해줍니다.

 

3. dfs를 이용하여 상어를 이동시키고, 이동한 좌표들을 box 배열에 저장합니다.

 

3. for문을 이용하여 vect 배열을 탐색하면서 상어가 지나간 자리에 있었던 물고기들의 좌표를 0으로 바꿔주고, 냄새를 남기고, 해당 좌표의 cnt 배열의 값을 0으로 경신합니다.

 

5. 냄새를 1 깎아줍니다.

 

6. temp 배열에 있는 물고기들의 좌표를 이용하여 cnt 배열을 갱신해주고, temp 배열에 남아있는 물고기들을 push 해줍니다.

 

7. vect 배열을 temp 배열로 초기화해줍니다.

 

8. 위 과정을 반복합니다.

 

[ 소스코드 ]

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
#include<vector>
 
using namespace std;
 
struct fish{
    int y;
    int x;
    int d;
};
 
int M, S;
int arr[5][5];    //상어 위치
int smell[5][5];    //냄새 위치
vector<fish> vect;
int fy[9] = { 0,0,-1,-1,-1,0,1,1,1 };    //물고기 방향 배열
int fx[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dy[4] = { -1,0,1,0 };        //상어 방향 배열
int dx[4] = { 0,-1,0,1 };
int cnt[5][5];    //물고기 수
int sy, sx;        //상어 좌표
pair<int,int> temp[3];
pair<int,int> box[3];
int Max;
 
void dfs(int y, int x, int level, int ans)    //상어 이동
{
    if (level == 3) {
        if (Max < ans) {
            Max = ans;
            for (int i = 0; i < 3; i++) {
                box[i] = temp[i];
            }
        }
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= 4 && xx > 0 && xx <= 4) {
            temp[level] = { yy,xx };
            int temp = cnt[yy][xx];
            cnt[yy][xx] = 0;
            dfs(yy, xx, level + 1, ans + temp);
            cnt[yy][xx] = temp;
        }
    }
}
 
void move()        //물고기 이동
{
    for (auto &next : vect) {
        int y = next.y;
        int x = next.x;
        int d = next.d;
        for (int i = 0; i < 8; i++) {
            int yy = y + fy[d];
            int xx = x + fx[d];
            if (yy > 0 && yy <= 4 && xx > 0 && xx <= 4) {
                if (arr[yy][xx] == 0 && smell[yy][xx] == 0) {
                    next.y = yy;
                    next.x = xx;
                    next.d = d;
                    cnt[y][x]--;
                    cnt[yy][xx]++;
                    break;
                }
            }
            d--;
            if (d <= 0) {
                d += 8;
            }
        }
    }
}
 
int main()
{
    scanf("%d %d", &M, &S);
 
    for (int i = 0; i < M; i++) {
        int y, x, d;
        scanf("%d %d %d", &y, &x, &d);
        vect.push_back({ y,x,d });
        cnt[y][x]++;
    }
 
    scanf("%d %d", &sy, &sx);
 
    arr[sy][sx] = 5;
 
    for(int s=0;s<S;s++){
        vector<fish> temp = vect;
 
        move();
 
        Max = -1;
 
        dfs(sy, sx, 0, 0);
        arr[sy][sx] = 0;
        sy = box[2].first;
        sx = box[2].second;
        arr[sy][sx] = 5;
 
        for (int i = 0; i < 3; i++) {
            cnt[box[i].first][box[i].second] = 0;
        }
 
        for (int i = 0; i < vect.size(); i++) {
            for (int j = 0; j < 3; j++) {
                if (vect[i].y == box[j].first && vect[i].x == box[j].second) {
                    smell[vect[i].y][vect[i].x] = 3;
                    cnt[vect[i].y][vect[i].x] = 0;
                    vect[i].y = 0;
                    break;
                }
            }
        }
 
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if (smell[i][j] > 0) {
                    smell[i][j]--;
                }
            }
        }
 
        for (int i = 0; i < temp.size(); i++) {
            cnt[temp[i].y][temp[i].x]++;
        }
 
        for (int i = 0; i < vect.size(); i++) {
            if (vect[i].y != 0) {
                temp.push_back({ vect[i].y, vect[i].x, vect[i].d });
            }
        }
 
        vect = temp;
    }
 
    printf("%d", vect.size());
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
반응형

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

 

21609번: 상어 중학교

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받습니다.

 

2. 0, 0 좌표부터 끝까지 2중 for문을 돌려서 무지개색이 아닌 블록부터 bfs를 시작하여 연결된 블록의 좌표와 포함된 무지개색 블록의 개수를 리턴합니다.

 

3. 만약 그룹이 있다면 블록을 부숴주고, 부순 개수의 제곱만큼 포인트를 더해줍니다.

 

4. 중력을 적용시키고, 반시계 방향으로 돌린 뒤 다시 중력을 적용시킵니다.

 

5. 위 과정을 반복해 주다가 그룹이 없다면 break 해줍니다.

 

6. point를 출력합니다.

 

[ 소스코드 ]

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int arr[21][21];
int temp[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int point;
 
struct status {
    vector<pair<int, int>> vect;
    int cnt;
};
 
void turn()        //반시계방향 회전
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[N - 1 - j][i] = arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = temp[i][j];
        }
    }
}
 
void gravity()        //중력 작용
{
    for (int i = 0; i < N; i++) {
        for (int j = N - 2; j >= 0; j--) {
            if (arr[j][i] >= 0 && arr[j + 1][i] == -2) {
                arr[j + 1][i] = arr[j][i];
                arr[j][i] = -2;
                j += 2;
            }
        }
    }
}
 
status bfs(int cury, int curx, int num)    //같은 색과 무지개 색의 블록 좌표, 무지개 색 블록 개수 return
{
    queue<pair<int, int>> q;
    vector<pair<int, int>> vect;
    q.push({ cury,curx });
    vect.push_back({ cury,curx });
    int visited[21][21] = { 0 };
    visited[cury][curx] = 1;
    int cnt = 0;
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        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] == 0 || arr[yy][xx] == num) && !visited[yy][xx]) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                    vect.push_back({ yy,xx });
                    if (arr[yy][xx] == 0) {
                        cnt++;
                    }
                    else {
                        temp[yy][xx] = 1;
                    }
                }
            }
        }
    }
 
    return { vect,cnt };
}
 
int main()
{
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
 
    while (1) {
        memset(temp, 0, sizeof(temp));
        status ans;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (temp[i][j] == 0 && arr[i][j] > 0) {
                    status temp = bfs(i, j, arr[i][j]);
 
                    if (ans.vect.size() < temp.vect.size()) {
                        ans = temp;
                    }
                    else if (ans.vect.size() == temp.vect.size()) {
                        if (ans.cnt <= temp.cnt) {
                            ans = temp;
                        }
                    }
                }
            }
        }
 
        for (auto next : ans.vect) {
            int y = next.first;
            int x = next.second;
            arr[y][x] = -2;
        }
 
        int size = ans.vect.size();
 
        if (size <= 1) {
            printf("%d", point);
            return 0;
        }
 
        point += size * size;
 
        gravity();
 
        turn();
 
        gravity();
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
[ 백준 ] 19236번 - 청소년 상어 (C++)  (0) 2022.09.29
반응형

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

 

20058번: 마법사 상어와 파이어스톰

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 구역을 나눕니다.

 

2. 나눈 구역을 temp 배열에 넣어 90도 회전해줍니다.

 

3. 회전시킨 temp 배열을 arr 배열에 갱신해줍니다.

 

4. 갱신된 arr배열을 바탕으로 temp 배열에 얼음의 양을 갱신해줍니다.

 

5. temp배열을 arr배열에 옮겨 주고 위를 반복합니다.

 

6. 위 과정이 끝나면 arr배열을 바탕으로 ans에 얼음의 양을 저장하고, bfs를 돌려 덩어리의 크기를 Max에 저장합니다.

 

[ 소스코드 ]

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
#include<cmath>
#include<queue>
 
using namespace std;
 
int N, Q;
int arr[64][64];
int temp[64][64];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs(int y, int x)    //덩어리 크기
{
    queue<pair<int, int>> q;
    q.push({ y,x });
 
    temp[y][x] = 0;
    int cnt = 1;
 
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        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 (temp[yy][xx] > 0) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                    cnt++;
                }
            }
        }
    }
 
    return cnt;
}
 
bool check(int y, int x)    //얼음이 주변에 3개 이상 있는지
{
    int cnt = 0;
 
    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] > 0) {
                cnt++;
            }
        }
    }
 
    if (cnt >= 3) {
        return true;
    }
    else {
        return false;
    }
}
 
void firestorm()    //파이어스톰 적용
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] > 0) {
                if (!check(i, j)) {
                    temp[i][j] = arr[i][j] - 1;
                }
                else {
                    temp[i][j] = arr[i][j];
                }
            }
            else {
                temp[i][j] = 0;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = temp[i][j];
        }
    }
}
 
void turn(int y, int x, int L)    //90도 회전
{
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < L; j++) {
            temp[i][j] = arr[y + i][x + j];
        }
    }
 
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < L; j++) {
            arr[y + i][x + L - j - 1] = temp[j][i];
        }
    }
}
 
void devide(int L)    //구역 나누기
{
    for (int i = 0; i < N; i += L) {
        for (int j = 0; j < N; j += L) {
            turn(i, j, L);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    N = pow(2, 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 < Q; i++) {
        int L;
        scanf("%d", &L);
        L = pow(2, L);
        devide(L);
 
        firestorm();
    }
 
    int ans = 0;
    int Max = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans += arr[i][j];
            if (temp[i][j] > 0) {
                int cnt = bfs(i, j);
                Max = max(cnt, Max);
            }
        }
    }
 
    printf("%d\n%d", ans, Max);
}
 
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17822번 - 원판 돌리기 (C++)  (0) 2022.09.25
[ 백준 ] 20057번 - 마법사 상어와 토네이도 (C++)  (0) 2022.09.24
[ 백준 ] 20056번 - 마법사 상어와 파이어볼 (C++)  (0) 2022.09.22
[ 백준 ] 17837번 - 새로운 게임 2 (C++)  (0) 2022.09.21
[ 백준 ] 1107번 - 리모컨 (C++)  (0) 2022.09.20
반응형

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받은 좌표를 1로 바꾸어 배추의 위치를 기록합니다.

 

2. bfs를 통해 배추가 있는 곳을 0으로 갱신해주면서 연결되어 있는 배추들의 개수를 cnt에 저장합니다.

 

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

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

[ 백준 ] 17837번 - 새로운 게임 2 (C++)  (0) 2022.09.21
[ 백준 ] 1107번 - 리모컨 (C++)  (0) 2022.09.20
[ 백준 ] 11723번 - 집합 (C++)  (0) 2022.09.18
[ 백준 ] 21610번 - 마법사 상어와 비바라기 (C++)  (0) 2022.09.17
[ 백준 ] 17779번 - 게리맨더링 2 (C++)  (0) 2022.09.16
반응형

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

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 조합을 이용하여 두 구역으로 나눕니다.

 

2. 각 구역에 있는 노드들끼리 연결되어 있는지 체크 후 연결되어 있다면 true를 반환하고 그렇지 않다면 false를 반환합니다.

 

3. true를 반환했다면 두 구역의 인구수 차를 ans와 비교하여 더 낮은 값을 ans에 저장합니다.

 

4. ans의 값이 초깃값이면 -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
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N;
int pop[11];
vector<int> list[11];
int population;
int box[11];
int cur;
int ans = 987654321;
 
bool bfs()    //두 구역으로 나누어지는 지 체크
{
    int visited[11] = { 0 };
    queue<int> q;
 
    for (int i = 1; i <= N; i++) {
        if (box[i] == 1) {
            q.push(i);
            break;
        }
    }
 
    while (!q.empty()) {    //첫번째 구역
        int cur = q.front();
        q.pop();
 
        if (box[cur] == 0) continue;
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (auto next : list[cur]) {
            if (visited[next] != 1) {
                q.push(next);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[i] != box[i]) return false;
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[i] != 1) {
            q.push(i);
            break;
        }
    }
 
    while (!q.empty()) {    //두번째 구역
        int cur = q.front();
        q.pop();
 
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (auto next : list[cur]) {
            if (visited[next] != 1) {
                q.push(next);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 0) return false;
    }
 
    return true;
}
 
void dfs(int level, int limit, int n)
{
    if (level == limit) {
        int temp = population - cur;
        int diff = abs(temp - cur);    //두 구역의 인구 차이
        if (bfs()) {    //두 구역으로 나누어 졌다면
            ans = min(diff, ans);
        }
 
        return;
    }
 
    for (int i = n; i <= N; i++) {    //조합 뽑기
        box[i] = 1;
        cur += pop[i];
        dfs(level + 1, limit, i + 1);
        box[i] = 0;
        cur -= pop[i];
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &pop[i]);
        population += pop[i];
    }
 
    for (int i = 1; i <= N; i++) {
        int num;
        scanf("%d", &num);
 
        for (int j = 0; j < num; j++) {
            int to;
            scanf("%d", &to);
            list[i].push_back(to);
        }
    }
 
    for (int i = 1; i <= N / 2; i++) {
        dfs(0,i,1);
    }
 
    if (ans == 987654321) {
        printf("%d", -1);
        return 0;
    }
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21608번 - 상어 초등학교 (C++)  (0) 2022.09.06
[ 백준 ] 11403번 - 경로 찾기 (C++)  (0) 2022.09.05
[ 백준 ] 1003번 - 피보나치 함수 (C++)  (0) 2022.09.03
[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02
[ 백준 ] 17135번 - 캐슬 디펜스 (C++)  (0) 2022.09.01

+ Recent posts

티스토리툴바