반응형

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

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. bfs를 이용하여 윗층과 아랫층으로 갔을 때의 층을 각각 queue에 push해 줍니다.

 

2. visited배열을 이용하여 이미 도착했던 층에 도착하면 무시해줍니다.

 

3. 원하는 층에 도착하면 버튼을 누른 횟수를 출력해줍니다.

 

4. 만약 queue가 빌 때까지 도착하지 못하면 use the stairs를 출력해줍니다.

 

[ 소스코드 ]

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<queue>
 
using namespace std;
 
int F, S, G, U, D;
int visited[1000001];
 
int main()
{
    scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
 
    queue<pair<int,int>> q;
    q.push({ S,0 });
    visited[S] = 1;
 
    while (!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (cur == G) {
            printf("%d", cnt);
            return 0;
        }
 
        if (cur+U <= F) {
            if (visited[cur + U] == 0) {
                visited[cur + U] = 1;
                q.push({ cur + U,cnt + 1 });
            }
        }
        if (cur-D > 0) {
            if (visited[cur - D] == 0) {
                visited[cur - D] = 1;
                q.push({ cur - D,cnt + 1 });
            }
        }
    }
 
    printf("use the stairs");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1956번 - 운동 (C++)  (0) 2022.10.11
[ 백준 ] 23291번 - 어항 정리 (C++)  (0) 2022.10.10
[ 백준 ] 17406번 - 배열 돌리기 4 (C++)  (0) 2022.10.08
[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
반응형

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

 

23289번: 온풍기 안녕!

유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 온풍기의 위치 배열, 벽의 위치 배열과 온도를 저장할 배열을 만들어 각각의 정보를 저장합니다.

 

2. 벽의 위치 배열의 경우 x, y 좌표에서 위 오른쪽 아래 왼쪽 방향에 벽이 있다면 각각 wall [ y ][ x ][ 0 ], wall [ y ][ x ][ 1 ], wall [ y ][ x ][ 2 ], wall [ y ][ x ][ 3 ]의 값을 1로 바꿔줍니다.

 

3. bfs를 활용하여 온풍기를 작동시킵니다.

 

4. 온도를 조절하고 초콜릿을 먹습니다.

 

5. 온도를 체크하는 위치에 온도가 모두 K이상이라면 현재 먹은 초콜릿의 개수를 출력합니다.

 

6. K이상이 될 때까지 위 과정을 반복합니다.

 

7. 만약 횟수가 100회를 초과한다면 101을 출력합니다.

 

[ 소스코드 ]

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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#include<iostream>
#include<queue>
 
using namespace std;
 
int R, C, K, W;
int arr[21][21];
int wall[21][21][4];    //벽의 위치 배열
int temp[21][21];
int tempT[21][21];
 
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
 
int dr[5][3] = {    //온풍기 방향 배열
    0,0,0,
    -1,0,1,
    -1,0,1,
    -1,-1,-1,
    1,1,1
};
int dc[5][3] = {
    0,0,0,
    1,1,1,
    -1,-1,-1,
    -1,0,1,
    -1,0,1
};
 
struct pos {
    int y;
    int x;
    int temp;
};
 
bool check()    //온도를 조사해야 하는 모든 칸의 온도가 K이상인지 체크
{
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (arr[i][j] == 5) {
                if (temp[i][j] < K) {
                    return false;
                }
            }
        }
    }
 
    return true;
}
 
void adjust()        //온도 조절
{
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            tempT[i][j] = temp[i][j];
        }
    }
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            for (int k = 0; k < 4; k++) {
                int yy = i + dy[k];
                int xx = j + dx[k];
                if (yy > 0 && yy <= R && xx > 0 && xx <= C && wall[i][j][k] != 1) {
                    if (temp[i][j] < temp[yy][xx]) {
                        int dif = temp[yy][xx] - temp[i][j];
                        tempT[i][j] += dif / 4;
                    }
                    else if(temp[i][j] > temp[yy][xx]){
                        int dif = temp[i][j] - temp[yy][xx];
                        tempT[i][j] -= dif / 4;
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            temp[i][j] = tempT[i][j];
        }
    }
 
    for (int i = 1; i <= R; i++) {
        if (temp[i][1] > 0) {
            temp[i][1]--;
        }
        if (temp[i][C] > 0) {
            temp[i][C]--;
        }
    }
 
    for (int i = 2; i < C; i++) {
        if (temp[1][i] > 0) {
            temp[1][i]--;
        }
        if (temp[R][i] > 0) {
            temp[R][i]--;
        }
    }
}
 
void bfs(int y, int x, int dir)    //온풍기 확산
{
    int visited[21][21] = { 0 };
    queue<pos> q;
    q.push({ y,x,5 });
    visited[y][x] = 1;
    temp[y][x] += 5;
 
    while (!q.empty()) {
        int cury = q.front().y;
        int curx = q.front().x;
        int curt = q.front().temp;
        q.pop();
 
        if (curt == 0) continue;
 
        for (int i = 0; i < 3; i++) {
            int yy = cury + dr[dir][i];
            int xx = curx + dc[dir][i];
            if (yy > 0 && yy <= R && xx > 0 && xx <= C) {
                bool flag = false;
                if (visited[yy][xx] != 1) {
                    if (dir == 1) {
                        if (wall[yy][xx][3] != 1) {
                            if (i == 0) {
                                if (wall[yy][xx - 1][2] != 1) {
                                    flag = true;
                                }
                            }
                            else if (i == 1) {
                                flag = true;
                            }
                            else {
                                if (wall[yy][xx - 1][0] != 1) {
                                    flag = true;
                                }
                            }
                        }
                    }
                    else if (dir == 2) {
                        if (wall[yy][xx][1] != 1) {
                            if (i == 0) {
                                if (wall[yy][xx + 1][2] != 1) {
                                    flag = true;
                                }
                            }
                            else if (i == 1) {
                                flag = true;
                            }
                            else {
                                if (wall[yy][xx + 1][0] != 1) {
                                    flag = true;
                                }
                            }
                        }
                    }
                    else if (dir == 3) {
                        if (wall[yy][xx][2] != 1) {
                            if (i == 0) {
                                if (wall[yy + 1][xx][1] != 1) {
                                    flag = true;
                                }
                            }
                            else if (i == 1) {
                                flag = true;
                            }
                            else {
                                if (wall[yy + 1][xx][3] != 1) {
                                    flag = true;
                                }
                            }
                        }
                    }
                    else {
                        if (wall[yy][xx][0] != 1) {
                            if (i == 0) {
                                if (wall[yy - 1][xx][1] != 1) {
                                    flag = true;
                                }
                            }
                            else if (i == 1) {
                                flag = true;
                            }
                            else {
                                if (wall[yy - 1][xx][3] != 1) {
                                    flag = true;
                                }
                            }
                        }
                    }
 
                    if (flag == true) {
                        visited[yy][xx] = 1;
                        temp[yy][xx] += curt - 1;
                        q.push({ yy,xx,curt - 1 });
                    }
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &R, &C, &K);
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    scanf("%d", &W);
 
    for (int i = 0; i < W; i++) {
        int x, y, t;
        scanf("%d %d %d", &y, &x, &t);
        if (t == 0) {
            wall[y][x][0] = 1;
            wall[y - 1][x][2] = 1;
        }
        else {
            wall[y][x][1] = 1;
            wall[y][x + 1][3] = 1;
        }
    }
 
    int ans = 0;
 
    while (1) {
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (arr[i][j] > 0 && arr[i][j] < 5) {
                    int yy = i + dr[arr[i][j]][1];
                    int xx = j + dc[arr[i][j]][1];
                    bfs(yy, xx, arr[i][j]);
                }
            }
        }
 
        adjust();
 
        ans++;
 
        if (ans > 100) {
            printf("%d", 101);
            return 0;
        }
 
        if (check()) {
            printf("%d", ans);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23290번 - 마법사 상어와 복제 (C++)  (0) 2022.10.05
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
반응형

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

 

23288번: 주사위 굴리기 2

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받습니다.

 

2. 주사위의 초기 상태를 하드 코딩합니다.

 

3. 각 방향별로 방향 배열을 만듭니다. (0:동쪽, 1:남쪽, 2:서쪽, 3:북쪽)

 

4. 주사위의 첫 방향은 동쪽이므로 동쪽으로 한 칸 움직입니다.

 

5. 이어져 있는 같은 숫자 * 그 개수만큼 점수를 더합니다.

 

6. 주사위 아랫면의 숫자와 맵의 숫자를 비교해 이동 방향을 결정합니다.

 

7. 해당 이동 방향으로 움직일 수 없을 시 정반대 방향으로 움직입니다.

 

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M, K;
int arr[20][20];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int dir;
int top = 1;
int dice[3][3] = {    //초기 주사위
    0,2,0,
    4,6,3,
    0,5,0
};
int y, x;
int ans;
 
int bfs(int y, int x)    //같은 숫자가 이어져 있는 개수 return
{
    queue<pair<int, int>> q;
    int visited[20][20] = { 0 };
    q.push({ y,x });
    visited[y][x] = 1;
    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 < M) {
                if (visited[yy][xx] != 1 && arr[y][x] == arr[yy][xx]) {
                    visited[yy][xx] = 1;
                    cnt++;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    return cnt;
}
 
void move(int dir)    //주사위 이동
{
    if (dir == 0) {
        int temp = top;
        top = dice[1][0];
        for (int i = 0; i < 2; i++) {
            dice[1][i] = dice[1][i + 1];
        }
        dice[1][2] = temp;
    }
    else if (dir == 1) {
        int temp = top;
        top = dice[0][1];
        for (int i = 0; i < 2; i++) {
            dice[i][1] = dice[i+1][1];
        }
        dice[2][1] = temp;
    }
    else if (dir == 2) {
        int temp = top;
        top = dice[1][2];
        for (int i = 2; i > 0; i--) {
            dice[1][i] = dice[1][i - 1];
        }
        dice[1][0] = temp;
    }
    else {
        int temp = top;
        top = dice[2][1];
        for (int i = 2; i > 0; i--) {
            dice[i][1] = dice[i - 1][1];
        }
        dice[0][1] = temp;
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < K; i++) {
        int yy = y + dy[dir];
        int xx = x + dx[dir];
 
        if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
            move(dir);
            ans += arr[yy][xx] * bfs(yy, xx);
        }
        else {
            dir += 2;
            if (dir > 3) dir %= 4;
            if (dir < 0) dir += 4;
            move(dir);
            yy = y + dy[dir];
            xx = x + dx[dir];
            ans += arr[yy][xx] * bfs(yy, xx);
        }
 
        y = yy;
        x = xx;
 
        if (arr[y][x] > dice[1][1]) {
            dir--;
        }
        else if (arr[y][x] < dice[1][1]) {
            dir++;
        }
        
        if (dir > 3) dir = 0;
        if (dir < 0) dir = 3;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23290번 - 마법사 상어와 복제 (C++)  (0) 2022.10.05
[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
반응형

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

 

[ 문제풀이 ]

 

bfs를 활용하여 문제를 풀었습니다.

 

1. 각 칸의 입력을 받으면서 값이 1이라면 queue에 넣습니다.

 

2. bfs를 돌리면서 cnt의 최댓값을 ans에 저장합니다.

 

3. arr배열에 있는 토마토 중 익지 않은 토마토가 하나라도 있다면 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[1000][1000];
int dy[4] = { -1,1,0,0 };
int dx[4] = {0, 0, -1, 1};
 
struct node {
    int y;
    int x;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &M, &N);
    queue<node> q;
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 1) {
                q.push({ i,j,0 });
            }
        }
    }
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        ans = max(ans, cnt);
 
        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] == 0) {    //익지 않은 토마토가 있다면
                    arr[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {        //안 익은 토마토가 하나라도 있으면
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) {
                printf("-1");
                return 0;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
반응형

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

 

16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net

 

 

[ 문제풀이 ]

 

bfs를 활용하여 문제를 풀었습니다.

 

1. 각 칸을 자신으로 초기화합니다.

 

2. 사다리와 뱀을 입력받습니다.

 

3. bfs를 활용하여 100번 칸에 도착하면 답을 출력하고 종료합니다.

 

위의 3번 과정을 진행할 때 한 번의 과정 동안 6번의 반복을 하면서 방문 여부를 체크해주고, 방문하지 않았다면 queue에 넣어 다음 과정을 진행해 줍니다.

 

[ 소스 코드 ]

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<queue>
 
using namespace std;
 
int N, M;
int arr[101];        //각 칸의 이동 위치
int visited[101];    //각 칸의 방문 여부
 
struct node {
    int cur;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= 100; i++) {    //각 칸의 이동 위치를 자신으로 초기화
        arr[i] = i;
    }
 
    for (int i = 0; i < N; i++) {    //사다리 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    for (int i = 0; i < M; i++) {    //뱀 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    queue<node> q;
    q.push({ 1, 0 });
 
    while (1)
    {
        int cur = q.front().cur;
        int cnt = q.front().cnt;
        q.pop();
 
        if (cur == 100) {    //100번 칸에 도착하면 cnt 출력 후 종료
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (int i = 1; i <= 6; i++) {
            int next = arr[cur + i];    //이동할 칸
            if (visited[next] != 1) {
                q.push({ next, cnt + 1 });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
반응형

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

각각의 문자에 따라 구역을 0으로 바꿔주는 함수를 만들어서 적록색약이 아닌 사람이 볼 수 있는 구역의 수를 구해줍니다. 그리고 R과 G를 한 구역으로 찾는 함수를 하나 더 만들어주어서 적록색약인 사람이 볼 수 있는 구역의 수를 출력해줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
 
struct node {
    int y;
    int x;
};
 
void bfs(int y, int x, char ch, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        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] == ch) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
void bfsRG(int y, int x, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        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] == 'R' || temp[yy][xx] == 'G') {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    char arr[101][101];
    char temp[101][101];
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 'R') {
                cnt++;
                bfs(i, j, 'R', temp);
            }
            else if (temp[i][j] == 'G') {
                cnt++;
                bfs(i, j, 'G', temp);
            }
            else if (temp[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', temp);
            }
        }
    }
 
    printf("%d ", cnt);
 
    cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'R' || arr[i][j] == 'G') {
                cnt++;
                bfsRG(i, j, arr);
            }
            else if (arr[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', arr);
            }
        }
    }
 
    printf("%d", cnt);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
반응형

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

 

[ 문제풀이 ]

 

재귀 함수를 통해서 벽을 세우고 bfs를 이용하여 바이러스를 퍼뜨린 후 안전 영역의 크기를 구해주면 되는 문제입니다.

 

맵의 최대 크기는 8 X 8 이므로 벽을 세우는데 최대 O(64*63*62)의 시간이 걸리므로 모든 경우의 수를 다 탐색하더라도 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
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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[8][8];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };
int ans;
 
struct pos {
    int y;
    int x;
};
 
int bfs(int map[][8])        //바이러스를 퍼트린 후 안전 영역의 크기를 출력
{
    queue<pos>q;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2) {
                q.push({ i,j });
            }
        }
    }
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        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 (map[yy][xx] == 0) {
                    map[yy][xx] = 2;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
void dfs(int level, int num)        //벽을 세우기 위한 재귀함수
{
    if (level == 3) {            //벽이 3개라면
        int temp[8][8] = { 0 };
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        int cnt = bfs(temp);
 
        if (ans < cnt) {
            ans = cnt;
        }
 
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (N * i + j > num) {        //이전에 벽을 세운 곳 다음부터 탐색
                if (arr[i][j] == 0) {
                    arr[i][j] = 1;
                    dfs(level + 1, i * N + j);
                    arr[i][j] = 0;
                }
            }
        }
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0, -1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
반응형

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

 

9328번: 열쇠

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

queue 두 개를 활용해서 bfs를 돌리면 쉽게 구할 수 있는 문제였습니다.

 

먼저 맵을 입력받을 때 탐색이 좀 더 쉽도록 배열의 1번 인덱스부터 w, h까지 입력을 받습니다. 그 이유는 가장 바깥쪽의 테두리는 자유롭게 다닐 수 있게 하여서 맵에 들어갈 수 있는 입구가 있다면 들어갈 수 있도록 설정하면 0, 0에서 시작하면 되기 때문입니다.

 

 

문을 만나면 키를 가지고 있는지 확인한 다음에 키가 있다면 그냥 열고 지나가고, 없다면 다음에 열쇠가 생겼을 때 열 수 있도록 door이라는 queue에 문의 좌표를 저장해 두었습니다.

 

그리고 키를 만나면 이 키로 열 수 있는 문이 있는지 체크하고 있다면 그 좌표를 q에 집어넣고, 없다면 그냥 지나가는 방법으로 문제를 풀었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
char arr[111][111];            //지도
int visited[111][111];        //방문 여부 체크
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int h, w;
        int key[26] = { 0 };        //몇번 키를 가지고 있는지 체크할 배열
        memset(visited, 0, sizeof(visited));
        memset(arr, 0, sizeof(arr));
        queue<pos> q;
        queue<pos> door[26];        //열쇠가 없는 문에 닿았을 때 좌표 저장
        int cnt = 0;
        cin >> h>> w;
 
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> arr[i][j];
            }
        }
 
        string str = "";
        cin >> str;
        if (str != "0") {
            for (int i = 0; i < str.size(); i++) {
                key[str[i] - 'a']++;
            }
        }
 
        q.push({ 0,0 });
        visited[0][0] = 1;
 
        while (!q.empty())
        {
            int y = q.front().y;
            int x = q.front().x;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int yy = y + dy[i];
                int xx = x + dx[i];
                if (yy >= 0 && yy <= h + 1 && xx >= 0 && xx <= w + 1) {
                    if (visited[yy][xx] == 1 || arr[yy][xx] == '*') continue;
                    visited[yy][xx] = 1;
                    
                    if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'Z') {
                        if (key[arr[yy][xx] - 'A'] == 1) {    //열쇠가 있다면 통과
                            q.push({ yy,xx });
                        }
                        else {
                            door[arr[yy][xx] - 'A'].push({ yy,xx });    //없다면 좌표를 저장
                        }
                    }
                    else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'z') {
                        key[arr[yy][xx] - 'a'] = 1;        //키를 가지고 있다고 체크
                        while (!door[arr[yy][xx] - 'a'].empty()) {    //키로 열 수 있는 문 좌표 q에 push
                            int curKey = arr[yy][xx] - 'a';
                            int curY = door[curKey].front().y;
                            int curX = door[curKey].front().x;
                            door[curKey].pop();
                            q.push({ curY,curX });
                        }
                        q.push({ yy,xx });
                    }
                    else if (arr[yy][xx] == '$') {        //문서면 cnt++
                        cnt++;
                        q.push({ yy,xx });
                    }
                    else {
                        q.push({ yy,xx });
                    }
                }
            }
        }
 
        cout << cnt << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 7662번 - 이중 우선순위 큐 (C++)  (0) 2022.06.17
반응형

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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

주어진 모눈종이의 테두리는 치즈가 없다고 하였으므로 0, 0부터 BFS를 돌려 치즈로 둘러싸여 있지 않은 공간들을 2로 초기화시켜주고 치즈들 중 2칸 이상 2에 닿아있는 치즈는 녹이면서 진행하였습니다.

 

그리고 다시 0, 0부터 BFS를 돌려 빈 공간들을 2로 초기화시켜주면서 위의 과정을 반복하고, 치즈가 다 사라지면 BFS를 돌린 횟수를 출력하였습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int map[100][100];
int visited[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
void bfs(int y, int x)        //치즈에 둘러쌓여 있지 않은 공간을 2로 초기화
{
    queue<pos> q;
    memset(visited, 0, sizeof(visited));
    q.push({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        map[curY][curX] = 2;
 
        for (int i = 0; i < 4; i++) {
            int yy = curY + dy[i];
            int xx = curX + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int check()        //치즈가 다 녹았는지 체크하는 함수
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int Cnt(int y, int x)    //실내 온도에 노출 된 횟수를 출력
{
    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 < M) {
            if (map[yy][xx] == 2) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    int cnt = 0;
 
    while (!check())        //치즈가 다 녹을 때까지
    {
        bfs(0, 0);        //0, 0부터 2로 빈 공간 2로 초기화
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {    //2칸 이상 닿아있다면 녹임
                    if (Cnt(i, j) >= 2) {
                        map[i][j] = 0;
                    }
                }
            }
        }
 
        cnt++;        //횟수 추가
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1865번 - 웜홀 (C++)  (0) 2022.06.10

+ Recent posts

티스토리툴바