알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다.
우리는 그럴때 이렇게 말한다.
백준 20056번 마법사 상어와 파이어볼 문제를 풀며 틀렸던 내용입니다.
기본적인 문제에 대한 설명과 해설은 레퍼런스에서 참고합니다.
이 글을 쓴 이유는 좌표처리 하며 생긴 생각의 오류를 남기기 위해서입니다.
마법사 상어가 쏜 파이어볼은 주어진 좌표체계에서 상하좌우 사방대각선으로 0에서 8까지의 방향으로 아래의 그림과 같이 움직입니다.
행을 y축 열을 x축이라고 생각했을때 각 방향으로의 좌표 변화는 다음과 같이 표현할 수 있습니다.
|
1
2
|
dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
dy = { 1, 1, 0, -1, -1, -1, 0, 1 };
|
cs |
그런데 문제가 발생합니다. 디버깅을 해보니 파이어볼이 위아래가 뒤집혀서 움직입니다.
저는 파이어볼을 좌표위치별로 담는 벡터 배열을 선언했는데 좌표변화에 따라서 배열 인덱스는 위로 가려면 -1 아래로 가려면 +1을 해야합니다. 평상시 생각하는 좌표 체계와 반대 방향이었던 거죠. 즉, 아래와 같아야 합니다.
|
1
2
|
dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
dy = { -1, -1, 0, 1, 1, 1, 0, -1 };
|
cs |
좌우에 해당하는 dx 는 똑같습니다. 위아래에 해당하는 dy가 반대입니다.
해당 문제에 대한 풀이를 찾아봤으나 이동 방향에 대한 이해가 잘 되지 않는 분들에게 도움이 되길 바랍니다.
문제
https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
문제풀이
https://na982.tistory.com/132?category=145346
[삼성 SW 역량 테스트] 마법사 상어와 파이어볼
마법사 상어와 파이어볼 강의 마법사 상어와 파이어볼 코드 #include #include using namespace std; struct FIREBALL { int y, x; int m, s, d; }; const int dy[8] = { -1, -1, 0, +1, +1, +1, 0, -1 }; const i..
na982.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
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
|
//https://www.acmicpc.net/problem/20056
#include <stdio.h>
#include <vector>
using namespace std;
/*
마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다.
i번 파이어볼의 위치는(ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다.위치(r, c)는 r행 c열을 의미한다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고,
1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
-> 좌표 순환
파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.
7 0 1
6 2
5 4 3
*/
int dc[8] = { 0, 1, 1, 1, 0, -1, -1 , -1 };
int dr[8] = { -1, -1, 0, 1, 1 , 1, 0, -1 };
/*
마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.
모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
*/
/*
마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.
*/
/*
4 ≤ N ≤ 50
0 ≤ M ≤ N^2
1 ≤ K ≤ 1,000
1 ≤ ri, ci ≤ N
1 ≤ mi ≤ 1,000
1 ≤ si ≤ 1,000
0 ≤ di ≤ 7
*/
//N = 격자크기, M = 파이어볼 수
int N, M, K;
struct fireballInfo {
//(r행,c열) 위치, m 질량, d 방향, s 속력
int r, c, m, s, d;
};
vector<fireballInfo> map[51][51];
vector<fireballInfo> ball;
//Move fireball until fireball list is empty
void move() {
//buf for saving next fireball information
vector<fireballInfo> nextMap[51][51];
fireballInfo current;
int S;
//check ball list
while (!ball.empty()) {
current = ball.back();
ball.pop_back();
//Modulation of Speed
S = current.s % N;
//Calculate coordinate
current.c = ((current.c - 1) + (dc[current.d] * S + N)) % N + 1;
current.r = ((current.r - 1) + (dr[current.d] * S + N)) % N + 1;
nextMap[current.r][current.c].push_back(current);
}
//copy nextMap to origin map
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
map[r][c] = nextMap[r][c];
}
}
}
/*
이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
파이어볼은 4개의 파이어볼로 나누어진다.
나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
질량이 0인 파이어볼은 소멸되어 없어진다.
*/
void mergeAndDivide() {
fireballInfo nextFireball;
//check how many balls are in the location of map
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
int even = true, odd = true, M = 0, S = 0;
if (map[r][c].size() == 0)
continue;
if (map[r][c].size() == 1) {
ball.push_back(map[r][c][0]);
continue;
}
//merge mass fireballs if there are two or more
for (int b = 0; b < map[r][c].size(); b++) {
M += map[r][c][b].m;
S += map[r][c][b].s;
if (map[r][c][b].d % 2 == 0)
odd = false;
else
even = false;
}
//Divide a ball into four with mass, direction and speed
nextFireball.r = r;
nextFireball.c = c;
nextFireball.m = M / 5;
int cnt = map[r][c].size();
if (nextFireball.m == 0)
continue;
nextFireball.s = S / cnt;
for (int i = 0; i < 4; i++) {
if (odd || even)
nextFireball.d = i * 2;
else
nextFireball.d = i * 2 + 1;
ball.push_back(nextFireball);
}
}
}
}
int solve() {
for(int m = 0; m < K; m++){
move();
mergeAndDivide();
}
int sum = 0;
for (int b = 0; b < ball.size(); b++) {
sum += ball[b].m;
}
return sum;
}
int main() {
int result = -1;
//Input
fireballInfo tmp;
/*
입력
첫째 줄에 N, M, K가 주어진다.
둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다.파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.
출력
마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.
*/
scanf("%d %d %d", &N, &M, &K);
for (int m = 0; m < M; m++) {
scanf("%d %d %d %d %d", &tmp.r, &tmp.c, &tmp.m, &tmp.s, &tmp.d);
ball.push_back(tmp);
}
//--------------------Solution--------------
result = solve();
//Output
printf("%d", result);
return 0;
}
|
cs |
'Technology > Problem Solving' 카테고리의 다른 글
| [PS]맞왜틀 시리즈5 변수 범위 (2) | 2022.05.21 |
|---|---|
| [PS]맞왜틀 시리즈4 초기화 (0) | 2022.05.21 |
| [PS]맞왜틀 시리즈3 정렬범위 (0) | 2022.05.20 |
| [PS]백준 14681 (0) | 2022.04.08 |
| [PS]맞왜틀 시리즈 1 지문 읽기, KOI 2차 2021 초1 사각형 면적 (0) | 2022.03.28 |