문제 URL : www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
문제를 보는데 이해하기가 너무 난해했네요 한국사람이 한국말보는데 여러번 읽어가며 읽어도 이해가 안되는 문장때문에 이해하느라 애먹었습니다. 그저 말을 좀 바꾸면 이해하기가 쉬울텐데라는 아쉬움..
제일 이해하기 어려웠던게
토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다.(???? 이게 한국말 문장이 좀이상해서 어렵게 이해하기가 힘들었습니다.)
라는문장을 제가 바꿔볼게여
토네이도가 x에서 y로 이동하면, y의 있는 모래가 사진에 나와있는 비율들 처럼 흩어진후 y의 남아있는 나머지 모래는 α가 적혀있는 칸으로 이동한다.
이렇게 말을바꾸니 이해가 되셨나요???
즉 이렇게
y가 100이라는 모래를 가지고 있고 토네이도 x가 왼쪽으로 움직일때 y의 모든모래가 그림처럼 흩어진 모래들을 다더해서 계산해보면 45입니다. 즉 100에서 -45를 하게되면 55가 되겠죠? 즉 y의 남은 모래 α가 55가 된다는겁니다.
그리고 y의 모래는 아예 0이되겠지요
그치만이것을 제공된 그림만 하면되는거냐? 아닙니다. 4가지 방향이있기때문에 4가지 모두 고려해야합니다.
이런식으로 그리고
토네이도는 결국엔 달팽이알고리즘의 역입니다.
달팽이 알고리즘은
LeetCode 59 Spiral Matrix II
문제 URL : leetcode.com/problems/spiral-matrix-ii/ 문제 접근법 : 기초적인 달팽이 알고리즘 문제입니다. c언어를 처음 접했을때 반복문 사용을 배우고나면 풀게되는 문제였었는데 그렇기 때문에 반복문을
congsoony.tistory.com
제가 올린 달팽이알고리즘을 참고하시고
역으로 시작을해야하기때문에 달팽이 알고리즘의 시작점부탁 끝지점까지 저장한후 반대로 탐색을 하면되기때문에
쉽게 접근할수있습니다. 그러나 방향은 토네이도가 어떤 방향으로 진행하는지 어떻게 알수있느냐?
그것은 현재 지점에서 이전지점의 차이를 구한다면 방향또한 쉽게 구할수있습니다.
소스코드 :
|
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
|
//By
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
vector<pair<int, int>> v;
int n;
int map[500][500];
int p[9] = { 5,10,10,2,7,7,2,1,1 };
int py[4][9] = {
{-2,-1,-1,0,0,0,0,1,1},
{0,-1,1,-2,-1,1,2,-1,1},
{2,1,1,0,0,0,0,-1,-1},
{0,1,-1,2,1,-1,-2,1,-1}
};
int px[4][9] = {
{0,-1,1,-2,-1,1,2,-1,1},
{2,1,1,0,0,0,0,-1 ,-1},
{0,1,-1,2,1,-1,-2,1,-1},
{-2,-1,-1,0,0,0,0,1,1}
};
void rotate() {//달팽이알고리즘 벡터에 방향을저장
int cnt = 0;
int y = -1, x = -1;
int board[500][500] = { 0 };
while (cnt < n * n) {
for (y++, x++; x < n&&!board[y][x]; x++) {
board[y][x] = ++cnt;
v.push_back({ y,x });
}
for (y++, x--; y < n && !board[y][x]; y++) {
board[y][x] = ++cnt;
v.push_back({ y,x });
}
for (y--, x--; x >= 0 && !board[y][x]; x--) {
board[y][x] = ++cnt;
v.push_back({ y,x });
}
for (y--, x++; y>=0 && !board[y][x]; y--) {
board[y][x] = ++cnt;
v.push_back({ y,x });
}
}
}
void input() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
}
int finddir(int cur) {
int y = v[cur].first - v[cur - 1].first; //현재와 이전의 차이를 통해 어느방향으로 흐르는지 알수있음
int x = v[cur].second - v[cur - 1].second;
for (int i = 0; i < 4; i++) {
if (dy[i] == y && dx[i] == x)
return i;
}
return -1;
}
bool isrange(int y,int x) {
return 0 <= y && y < n && 0 <= x && x < n;
}
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void solve() {
reverse(v.begin(), v.end());//달팽이 알고리즘으로 저장했던 배열을 거꾸로
int result = 0;
for (int i = 1; i < v.size(); i++) {
int y = v[i].first;
int x = v[i].second;
int dir = finddir(i);
int sum = 0; //흩어진 모래의양
for (int j = 0; j < 9; j++) {
int ny = y + py[dir][j];
int nx = x + px[dir][j];
int value = (map[y][x] * p[j]) / 100;
if (!isrange(ny, nx))//완전히 밖으로나간 모래
result += value;
else
map[ny][nx] += value;
sum += value;
}
//마지막은 현재 모래를 움직이는 방향으로 보내기
int ny = y + dy[dir];
int nx = x + dx[dir];
int value = map[y][x] - sum;
if (!isrange(ny, nx))
result += value;
else
map[ny][nx] += value;
map[y][x] = 0;//모래들의 흩어졌으니 현재 모래는 0이 되야함
}
cout << result << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
rotate();
solve();
}
|
cs |
궁금한점 혹은 모르는점 혹은 또 다른아이디어등 다양한 댓글은 언제든 환영입니다.
'백준' 카테고리의 다른 글
| 백준 16920 확장 게임 (0) | 2021.02.15 |
|---|---|
| 백준 1806 부분합 (0) | 2021.02.15 |
| 백준 3190 뱀 (0) | 2021.02.10 |
| 백준 1525 퍼즐 (0) | 2021.01.01 |
| 벡즌 1929 소수 구하기 (0) | 2021.01.01 |
