반응형

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

 

23291번: 어항 정리

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 어항을 저장할 배열 arr [ 10 ][ 101 ]을 만듭니다.

 

2. 주어진 조건에 따라 어항을 정리합니다.

 

3. 가장 큰 값과 가장 작은 값의 차이가 K이하가 될 때까지 위 과정을 반복합니다.

 

4. K이하가 되었을 때 어항을 정리한 횟수를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int N, K;
int arr[10][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void put()    //어항을 일렬로 만드는 함수
{
    int temp[101] = { 0 };
    int cur = 1;
 
    for (int i = 1; i <= N ; i++) {
        for (int j = 9; j >= 0; j--) {
            if (arr[j][i] == 0) break;
            temp[cur] = arr[j][i];
            cur++;
        }
    }
 
    memset(arr, 0, sizeof(arr));
 
    for (int i = 1; i < cur; i++) {
        arr[9][i] = temp[i];
    }
}
 
void turn(int arr[][10], int num)    //배열을 시계방향으로 90도 회전
{
    int temp[10][10] = { 0 };
 
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            temp[j][num - i - 1] = arr[i][j];
        }
    }
 
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            arr[i][j] = temp[i][j];
        }
    }
}
 
void airRoll()    //첫 공중부양
{
    int cur = 1;
    for (int i = 1; i <= 10; i++) {
        int temp[10][10] = { 0 };
 
        if (cur + 2 * i - 1 > N) return;
 
        for (int j = cur; j < cur + i; j++) {
            for (int k = 10-i; k < 10; k++) {
                temp[k+i-10][j-cur] = arr[k][j];
                arr[k][j] = 0;
            }
        }
 
        turn(temp, i);
 
        cur += i;
 
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < i; k++) {
                arr[9-i+j][cur+k] = temp[j][k];
            }
        }
 
        if (cur + 2*i > N) return;
 
        for (int j = cur; j < cur + i; j++) {
            for (int k = 9 - i; k < 10; k++) {
                temp[k+i-9][j - cur] = arr[k][j];
                arr[k][j] = 0;
            }
        }
 
        turn(temp, i+1);
 
        cur += i;
 
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < i+1; k++) {
                arr[9 - i + j][cur + k] = temp[j][k];
            }
        }
    }
}
 
void air()    //두번째 공중부양
{
    int cur = 1;
 
    for (int i = N/2; i > 0; i--) {
        arr[8][N / 2 + cur] = arr[9][i];
        cur++;
        arr[9][i] = 0;
    }
 
    cur = 1;
 
    for (int i = N / 4 * 3; i > N / 2; i--) {
        arr[6][N / 4 * 3 + cur] = arr[9][i];
        arr[7][N / 4 * 3 + cur] = arr[8][i];
        arr[9][i] = 0;
        arr[8][i] = 0;
        cur++;
    }
 
}
 
void adjust()    //물고기 수 조절
{
    int temp[10][101] = { 0 };
 
    for (int i = 0; i < 10; i++) {
        for (int j = 1; j <= N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < 10; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] > 0) {
                for (int k = 0; k < 4; k++) {
                    int yy = i + dy[k];
                    int xx = j + dx[k];
                    if (yy >= 0 && yy < 10 && xx > 0 && xx <= N) {
                        if (arr[yy][xx] > 0) {
                            if (arr[i][j] > arr[yy][xx]) {
                                int dif = arr[i][j] - arr[yy][xx];
                                dif /= 5;
                                if (dif > 0) {
                                    temp[i][j] -= dif;
                                    temp[yy][xx] += dif;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        for (int j = 1; j <= N; j++) {
            arr[i][j] = temp[i][j];
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[9][i]);
    }
 
    int cnt = 0;
 
    while (1) {
        int Min = 987654321;
        int Max = 0;
        for (int i = 1; i <= N; i++) {
            Min = min(Min, arr[9][i]);
            Max = max(Max, arr[9][i]);
        }
 
        if (Max - Min <= K) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 1; i <= N; i++) {
            if (arr[9][i] == Min) arr[9][i]++;
        }
 
        airRoll();
 
        adjust();
 
        put();
 
        air();
 
        adjust();
 
        put();
 
        cnt++;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17472번 - 다리 만들기 2 (C++)  (0) 2022.10.12
[ 백준 ] 1956번 - 운동 (C++)  (0) 2022.10.11
[ 백준 ] 5014번 - 스타트링크 (C++)  (0) 2022.10.09
[ 백준 ] 17406번 - 배열 돌리기 4 (C++)  (0) 2022.10.08
[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
반응형

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

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연산의 개수를 저장할 구조체를 만들고 배열에 연산을 저장합니다.

 

2. 순열을 뽑아서 연산을 진행하면서 최솟값을 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
#include<iostream>
 
using namespace std;
 
struct pos {
    int r;
    int c;
    int s;
};
 
int N, M, K;
int arr[51][51];
pos cal[6];
int visited[6];
int ans = 987654321;
 
void lotate(pos cur)    //배열 돌리가
{
    int r, c, s;
    r = cur.r;
    c = cur.c;
    s = cur.s;
 
    
    for (int i = s; i > 0; i--) {
        int temp = arr[r - i][c - i];
        for (int j = r - i; j < r + i; j++) {
            arr[j][c - i] = arr[j + 1][c - i];
        }
        for (int j = c - i; j < c + i; j++) {
            arr[r + i][j] = arr[r + i][j + 1];
        }
        for (int j = r + i; j > r - i; j--) {
            arr[j][c + i] = arr[j - 1][c + i];
        }
        for (int j = c + i; j > c - i; j--) {
            arr[r - i][j] = arr[r - i][j - 1];
        }
        arr[r - i][c - i + 1] = temp;
    }
 
    int de = -1;
}
 
void dfs(int level)    //순열 뽑기
{
    if (level == K) {
        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= M; j++) {
                sum += arr[i][j];
            }
            ans = min(ans, sum);
        }
        return;
    }
 
    int temp[51][51] = { 0 };
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < K; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            lotate(cal[i]);
            dfs(level + 1);
            visited[i] = 0;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    arr[i][j] = temp[i][j];
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < K; i++) {
        int r, c, s;
        scanf("%d %d %d", &r, &c, &s);
        cal[i] = { r,c,s };
    }
 
    dfs(0);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23291번 - 어항 정리 (C++)  (0) 2022.10.10
[ 백준 ] 5014번 - 스타트링크 (C++)  (0) 2022.10.09
[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23290번 - 마법사 상어와 복제 (C++)  (0) 2022.10.05
반응형

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

 

17281번: ⚾

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 순열을 통해 타자의 순서를 정합니다.

 

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[51][10];
int order[10];
int visited[10];
int ans;
 
int getScore()        //야구 진행
{
    int cur = 1;
    int score = 0;
    for (int i = 1; i <= N; i++) { //이닝 번호
        int out = 0;
        int base[4] = { 0 };
 
        while (out < 3) {    //out카운트가 3이 될 때까지
            int player = order[cur];
            base[0] = 1;
            if (arr[i][player] == 0) {    //아웃
                out++;
            }
            else {    //진루
                for (int j = 3; j >= 0; j--) {
                    if (base[j] == 0) {
                        continue;
                    }
                    else {
                        if (j + arr[i][player] > 3) {
                            score++;                        }
                        else {
                            base[j + arr[i][player]] = 1;
                        }
                        base[j] = 0;
                    }
                }
            }
 
            cur++;
            if (cur > 9) cur = 1;
        }
    }
 
    return score;
}
 
void dfs(int level)
{
    if (level == 5 && order[4] != 1) {    //4번 타자가 1번 사람이 아니라면
        return;
    }
    if (level == 10) {
        ans = max(ans, getScore());
        return;
    }
 
    for (int i = 1; i <= 9; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            order[level] = i;
            dfs(level + 1);
            visited[i] = 0;
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 9; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dfs(1);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5014번 - 스타트링크 (C++)  (0) 2022.10.09
[ 백준 ] 17406번 - 배열 돌리기 4 (C++)  (0) 2022.10.08
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23290번 - 마법사 상어와 복제 (C++)  (0) 2022.10.05
[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
반응형

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

 

19238번: 스타트 택시

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 저장할 arr배열을 만들어 초기화합니다.

 

2. 손님의 출발지와 목적지를 start 배열과 des배열에 각각 저장합니다.

 

3. 손님의 도착 여부를 box 배열에 저장합니다.

 

4. 모든 손님들을 돌아가며 가장 가까운 손님을 찾아 이동합니다.

 

5. 손님의 목적지로 이동하고 남은 연료를 계산합니다.

 

6. 목적지로 이동할 수 없는 경우 -1을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M, F;
int arr[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int curY, curX;
pair<int, int> start[401];
pair<int, int> des[401];
int box[401];
 
struct pos {
    int y;
    int x;
    int cnt;
};
 
int bfs(int y, int x, int desY, int desX)    //목적지 까지의 거리 return
{
    queue<pos> q;
    q.push({ y,x,0 });
    int visited[21][21] = { 0 };
    visited[y][x] = 1;
 
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        if (y == desY && x == desX) {
            return 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 <= N) {
                if (arr[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &F);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    scanf("%d %d", &curY, &curX);
 
    for (int i = 1; i <= M; i++) {
        scanf("%d %d %d %d", &start[i].first, &start[i].second, &des[i].first, &des[i].second);
    }
 
    while (1) {
        int destination = 0;
        int min = 987654321;
        for (int i = 1; i <= M; i++) {
            if (box[i] != 1) {
                int temp = bfs(curY, curX, start[i].first, start[i].second);
                if (min > temp) {    //더 가까우면
                    min = temp;
                    destination = i;
                }
                else if (min == temp) {        //거리가 같다면
                    if (start[destination].first > start[i].first) {
                        destination = i;
                    }
                    else if (start[destination].first == start[i].first) {
                        if (start[destination].second > start[i].second) {
                            destination = i;
                        }
                    }
                }
            }
            if (min <= 0) break;
        }
 
        if (min == -1) {    //목적지로 갈 수 없다면
            printf("%d", -1);
            return 0;
        }
 
        curY = start[destination].first;
        curX = start[destination].second;
        F -= min;
        box[destination] = 1;
 
        if (F <= 0) {    //연료가 다 떨어지면
            printf("%d", -1);
            return 0;
        }
 
        int temp = bfs(curY, curX, des[destination].first, des[destination].second);
 
        if (temp == -1) {
            printf("%d", -1);
            return 0;
        }
 
        F -= temp;
 
        if (F < 0) {
            printf("%d", -1);
            return 0;
        }
 
        curY = des[destination].first;
        curX = des[destination].second;
 
        F += (temp * 2);
 
        int cnt = 0;
 
        for (int i = 1; i <= M; i++) {
            if (box[i] == 1) {
                cnt++;
            }
        }
 
        if (cnt == M) break;
    }
 
    printf("%d", F);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
[ 백준 ] 19236번 - 청소년 상어 (C++)  (0) 2022.09.29
[ 백준 ] 20061번 - 모노미노도미노 2 (C++)  (0) 2022.09.28
반응형

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

 

19237번: 어른 상어

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 냄새를 남길 수 있게 smell struct를 만들어 상어의 번호와 남은 시간을 저장합니다.

 

2. 상어의 위치를 shark struct를 만들어 현재 좌표와 방향을 저장합니다.

 

3. arr 배열을 통해서 현재 상어의 위치 상태를 확인합니다.

 

4. 상어가 먼저 냄새를 남깁니다.

 

5. 규칙에 따라 이동해줍니다. 여기서 이동할 수 있는 모든 방향에 냄새가 있다면 이동 우선순위에 따라서 본인의 냄새가 있던 곳으로 이동해 주어야 합니다.

 

6. 1번 상어가 남을 때까지 위 과정을 반복하고, 1번 상어만 남았을 때는 걸린 시간을 출력해줍니다.

 

7. 만약 1000초가 넘어도 1번 상어만 남지 않을 경우 -1을 출력해줍니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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
#include<iostream>
 
using namespace std;
 
struct shark {        //상어의 상태
    int y;
    int x;
    int dir;
};
 
struct smell {        //냄새 주인과 남은 시간
    int num;
    int k;
};
 
int N, M, k;
int dy[5] = { 0,-1,1,0,0 };
int dx[5] = { 0,0,0,-1,1 };
int arr[20][20];
int priority[401][5][4];
smell map[20][20];
shark pos[401];
 
void move()        //상어 움직임
{
    for (int i = 1; i <= M; i++) {
        bool flag = false;
        if (pos[i].y != -1) {
            for (int j = 0; j < 4; j++) {
                int dir = priority[i][pos[i].dir][j];
                int yy = pos[i].y + dy[dir];
                int xx = pos[i].x + dx[dir];
                if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                    if (map[yy][xx].num == 0) {    //냄새가 없는 장소가 있다면
                        arr[pos[i].y][pos[i].x] = 0;
                        if (arr[yy][xx] == 0) {    //그 장소에 아무도 없다면
                            pos[i] = { yy,xx,dir };
                            arr[yy][xx] = i;
                        }
                        else if (arr[yy][xx] < i) {    //그 장소에 나보다 센 상어가 있다면
                            pos[i] = { -1,-1,-1 };
                        }
                        else if (arr[yy][xx] > i){    //그 장소에 나보다 약한 상어가 있다면
                            pos[arr[yy][xx]] = { -1,-1,-1 };
                            pos[i] = { yy,xx,dir };
                            arr[yy][xx] = i;
                        }
                        flag = true;
                        break;
                    }
                }
            }
            if (flag == false) {    //냄새가 모두 둘러싸고 있다면
                for (int j = 0; j < 4; j++) {
                    int dir = priority[i][pos[i].dir][j];
                    int yy = pos[i].y + dy[dir];
                    int xx = pos[i].x + dx[dir];
                    if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                        if (map[yy][xx].num == i) {    //나의 냄새가 있는 곳으로
                            arr[pos[i].y][pos[i].x] = 0;
                            pos[i] = { yy,xx,dir };
                            arr[yy][xx] = i;
                            break;
                        }
                    }
                }
            }
        }
    }
}
 
void smells()
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j].num != 0) {
                map[i][j].k--;
                if (map[i][j].k == 0) {
                    map[i][j].num = 0;
                }
            }
        }
    }
 
    for (int i = 1; i <= M; i++) {
        if (pos[i].y != -1) {
            map[pos[i].y][pos[i].x] = { i, k };
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &k);
 
    for (int i = 0; i < N; i++)    {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            pos[arr[i][j]] = { i,j };
        }
    }
 
    for (int i = 1; i <= M; i++) {
        int dir;
        scanf("%d", &dir);
 
        pos[i].dir = dir;
    }
 
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 0; k < 4; k++) {
                int dir;
                scanf("%d", &dir);
 
                priority[i][j][k] = dir;
            }
        }
    }
 
    int ans = 0;
 
    while (1) {
        ans++;
        smells();
 
        move();
 
        int cnt = 0;
 
        for (int i = 1; i <= M; i++) {
            if (pos[i].y != -1) {
                cnt++;
            }
        }
 
        if (cnt == 1) {    //1번 상어만 남는다면
            printf("%d", ans);
            return 0;
        }
 
        if (ans == 1000) {    //1000번을 넘으면
            printf("%d", -1);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19236번 - 청소년 상어 (C++)  (0) 2022.09.29
[ 백준 ] 20061번 - 모노미노도미노 2 (C++)  (0) 2022.09.28
[ 백준 ] 17825번 - 주사위 윷놀이 (C++)  (0) 2022.09.27
반응형

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

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 상어를 17번으로 설정하고, 각각의 물고기의 위치와 방향을 pos배열에 저장해줍니다.

 

2. arr 배열을 통해서 현재 공간의 상태를 저장해 줍니다.

 

3. 상어가 0, 0에 있는 물고기를 먹고, 먹은 물고기의 방향을 가집니다.

 

4. 물고기가 규칙에 따라 움직입니다.

 

5. 이후 상어가 움직여 물고기를 먹습니다.

 

6. 위 과정을 반복하다가 상어가 움직이지 못하는 상황이 오면 현재까지 먹은 물고기의 번호의 합을 ans에 저장합니다.

 

[ 소스코드 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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
#include<iostream>
 
using namespace std;
 
int dy[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dx[9] = { 0,0,-1,-1,-1,0,1,1,1 };
 
struct fish {
    int y;
    int x;
    int dir;
};
 
int arr[4][4];
fish pos[18];
int ans;
 
void move()        //물고기 이동
{
    for (int i = 1; i <= 16; i++) {
        if (pos[i].y != -1) {
            int y = pos[i].y;
            int x = pos[i].x;
            int dir = pos[i].dir;
            for (int j = 0; j < 8; j++) {
                int yy = y + dy[dir];
                int xx = x + dx[dir];
                if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4) {
                    if (arr[yy][xx] == 0) {    //빈칸일 때
                        arr[yy][xx] = arr[y][x];
                        arr[y][x] = 0;
                        pos[i] = { yy,xx, dir };
                        break;
                    }
                    else if (arr[yy][xx] != 17) {    //상어가 있을 때
                        int temp = arr[yy][xx];
                        arr[yy][xx] = arr[y][x];
                        arr[y][x] = temp;
 
                        pos[arr[yy][xx]] = { yy,xx,dir };
                        pos[arr[y][x]].y = y;
                        pos[arr[y][x]].x = x;
                        break;
                    }
                    else {    //이동이 불가할 때
                        dir++;
                    }
                }
                else {    //이동이 불가할 때
                    dir++;
                }
                if (dir > 8) {
                    dir = 1;
                }
            }
        }
    }
}
 
void dfs(int cnt)
{
    ans = max(ans, cnt);    //먹은 물고기 번호의 합
 
    move();
    
    int temp[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    fish tempPos[18];
    for (int i = 1; i <= 17; i++) {
        tempPos[i] = pos[i];
    }
 
    int y = pos[17].y;
    int x = pos[17].x;
    int dir = pos[17].dir;
    int tempCnt = cnt;
 
    for (int i = 1; i < 4; i++) {
        int yy = y + dy[dir] * i;
        int xx = x + dx[dir] * i;
        if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4) {
            if (arr[yy][xx] != 0) {    //물고기를 먹었을 때
                pos[17] = { yy,xx,pos[arr[yy][xx]].dir };
                cnt += arr[yy][xx];
                pos[arr[yy][xx]] = { -1,-1,-1 };
                arr[yy][xx] = 17;
                arr[y][x] = 0;
                dfs(cnt);
                cnt = tempCnt;
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        arr[i][j] = temp[i][j];
                    }
                }
                for (int i = 1; i <= 17; i++) {
                    pos[i] = tempPos[i];
                }
            }
        }
    }
}
 
int main()
{
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int num, dir;
            scanf("%d %d", &num, &dir);
 
            arr[i][j] = num;
            pos[num] = { i,j,dir };
        }
    }
 
    pos[17] = { 0,0, pos[arr[0][0]].dir };    //처음 0, 0에서 물고기를 먹었을 때
    pos[arr[0][0]] = { -1,-1,-1 };
    int cnt = arr[0][0];
    arr[0][0] = 17;
    
    dfs(cnt);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
[ 백준 ] 20061번 - 모노미노도미노 2 (C++)  (0) 2022.09.28
[ 백준 ] 17825번 - 주사위 윷놀이 (C++)  (0) 2022.09.27
[ 백준 ] 21611번 - 마법사 상어와 블리자드 (C++)  (0) 2022.09.26

+ Recent posts

티스토리툴바