💡 구현/시뮬레이션
Memory 2996KB Time 420ms Code Length 2525B
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
#include <iostream>
#include <queue>
using namespace std;
int R, C, M;
long long int score;
struct info {
int r, c, s, d, z;
};
struct cmp {
bool operator()(info second, info first) {
if (first.c < second.c) {
return true;
}
else if (first.c == second.c) {
if (first.r < second.r) {
return true;
}
else if (first.r == second.r) {
if (first.z > second.z) {
return true;
}
}
}
return false;
};
};
priority_queue<info, vector<info>, cmp> sharks; // c가 작고 r이작고 크기가 큰 순서대로
void init() {
cin >> R >> C >> M;
for (int i = 0; i < M; i++) {
int r, c, s, d, z;
cin >> r >> c >> s >> d >> z;
sharks.push({ r - 1, c - 1, s, d - 1, z });
}
score = 0;
}
void cpyqueue(priority_queue<info, vector<info>, cmp> &q1, queue<info> &q2) {
while (!q2.empty()) {
info tmp = q2.front();
q2.pop();
q1.push(tmp);
}
}
void getshark(int x) { // 상어 끌어 올리기
queue<info> eq;
int flag = 0;
while (!sharks.empty()) {
info shark = sharks.top();
sharks.pop();
if (flag == 0 && shark.c == x) { // 한번에 한해서
score += shark.z;
flag = 1;
}
else {
eq.push(shark);
}
}
cpyqueue(sharks, eq);
}
void move_shark() {
priority_queue<info, vector<info>, cmp> eq; // c가 작고 r이작고 크기가 큰 순서대로
const int dy[] = { -1,1,0,0 }; // 위 아래 오른 왼
const int dx[] = { 0,0,1,-1 };
int visited[100][100] = {}; // 방문 했으면 패스
while (!sharks.empty()) {
info shark = sharks.top();
sharks.pop();
int Rotate;
if (shark.d == 0 || shark.d == 1) { // 위 아래 움직일 시.
Rotate = shark.s % ((R - 1) * 2);
}
else { // 오른 왼 움직일 시.
Rotate = shark.s % ((C - 1) * 2);
}
while (Rotate--) {
int ny = shark.r + dy[shark.d];
int nx = shark.c + dx[shark.d];
if (ny >= R || nx >= C || ny < 0 || nx < 0) { // 범위 초과시 방향전환
if (shark.d == 0) shark.d = 1;
else if (shark.d == 1) shark.d = 0;
else if (shark.d == 2) shark.d = 3;
else if (shark.d == 3) shark.d = 2;
ny = shark.r + dy[shark.d];
nx = shark.c + dx[shark.d];
}
shark.r = ny;
shark.c = nx;
}
eq.push(shark); // 옮겨 담음
}
while (!eq.empty()) {
info shark = eq.top();
eq.pop();
if (visited[shark.r][shark.c] == 1) continue; // 큰 상어가 이미 방문했으므로
visited[shark.r][shark.c] = 1;
sharks.push(shark);
}
}
int main() {
init();
for (int i = 0; i < C; i++) {
getshark(i);
move_shark();
}
cout << score;
}
이 코드는 상어들의 움직임을 시뮬레이션하여 가장 오른쪽 열부터 상어를 잡아 먹는 과정을 구현한다.
먼저 상어의 정보를 입력받고, 큐에 상어들을 크기가 큰 순서대로 저장한다. 그 후에 각 열마다 상어를 잡아 먹는 함수를 호출하고, 상어들을 이동시키는 함수를 실행한다. 이동할 때 상어가 벽을 넘어가면 방향을 바꾸어 이동하도록 처리한다. 이 과정을 모든 열에 대해 반복한 뒤, 총 점수를 출력한다.
처음에는 Queue와 Priority Queue를 사용해서 크기가 큰 상어들을 상단 큐에 배치하고, visited 배열을 사용하여 이미 방문한 흔적이 있다면 큰 상어가 이미 해당 (r,c)좌표에 방문을 해있는 상태이기 때문에 이후에 방문하는 상어는 방문을 무시하는 형태로 작성을 하였다.
이 코드에는 두 가지 문제가 존재했다.
첫 번째는 Queue의 자료구조 특성 상 Queue를 전부 뽑아 다른 큐에 옮겨 담아야 하기에 Queue가 두개 이상 존재 해야 했다. 이 부분은 Vector를 사용하여 상어가 죽었는지 유무를 체크하는 방법이 있었다.
두 번째는 상어를 옮기는 방법에 대해서 일일이 한 칸씩 옮겨주었기에 시간이 더 걸렸을 것이다. 상어를 옮기는 방법은 상어가 이동해야 하는 속도를 다시 원위치로 돌아오는 횟수(세로의 경우 (R-1)2 번, 가로의 경우 (C-1)2번)로 나눈 나머지 값에 대해, 기존 (R,C)에서 해당 방향으로 이동했을 때 범위를 초과하는 지 안 하는 지를 체크하여 적절히 거리 이동을 해주었다면 시간이 더 줄었을 것같다.
말로 적으면 이해가 잘 안되니 예제를 하나 들고 왔다.
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
#include <iostream>
using namespace std;
int N,M, numOfShark;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
typedef struct shark{
int size;
int dir;
int speed;
}SHARK;
SHARK sharkMap[100][100];
void solve();
int main(void){
//칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다
//1,1 원점
/*1.낚시왕이 오른쪽으로 한 칸 이동한다.
2.낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3.상어가 이동한다.
*/
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>N>>M>>numOfShark;
for(int i=0,r,c,s,d,z; i<numOfShark;i++){
cin>>r>>c>>s>>d>>z;
sharkMap[r-1][c-1].speed=s;
sharkMap[r-1][c-1].dir=d-1;
sharkMap[r-1][c-1].size=z;
}
solve();
}
int getShark(int ix){
for(int j=0;j<N;j++){
if(sharkMap[j][ix].size>0){
int size=sharkMap[j][ix].size;
sharkMap[j][ix].size=0;
sharkMap[j][ix].speed=0;
sharkMap[j][ix].dir=0;
return size;
}
}
//없을 수 도 있음
return 0;
}
bool outOfRange(int y,int x){
if(y<0||x<0||y>=N||x>=M) return true;
return false;
}
void printSharK(){
cout<<"LOCATION of SHARK\n";
for(int i=0;i<N;i++){
for(int s=0;s<M;s++){
cout<<sharkMap[i][s].size<<" ";
}
cout<<"\n";
}
}
int moveEachShark(int&y,int&x,int&dir,int speed){
//안움직임
if(speed==0) return 1;
if(dir<2){ //위 아래
int divider=(N-1)*2;
speed%=divider;
}
else{
//좌 우
int divider=(M-1)*2;
speed%=divider;
}
if(!outOfRange(y+(speed*dy[dir]),x+(speed*dx[dir]))){
y+=(speed*dy[dir]);
x+=(speed*dx[dir]);
return 1;
}
for(int i=0;i<speed;i++){
y+=dy[dir];
x+=dx[dir];
if(outOfRange(y,x)){
if(dir%2==0) dir++;
else dir--;
//if(dir=2) dir
y+=(2*dy[dir]);
x+=(2*dx[dir]);
}
}
if(outOfRange(y,x)) return -1;
return 1;
}
void moveShark(){
SHARK copySharkMap[100][100];
//초기화
for(int i=0;i<N;i++){
for(int s=0;s<M;s++){
copySharkMap[i][s].size=0;
copySharkMap[i][s].speed=0;
copySharkMap[i][s].dir=0;
}
}
for(int i=0;i<N;i++){
for(int s=0;s<M;s++){
if(sharkMap[i][s].size>0){
int y=i;
int x=s;
int dir=sharkMap[i][s].dir;
int speed=sharkMap[i][s].speed;
int size=sharkMap[i][s].size;
int result=moveEachShark(y,x,dir,speed);
if(result==-1){
cout<<y<<" "<<x<<" "<<dir<<" "<<speed<<" "<<size<<"\n";
cout<<"OUTOFRANGE\n";
return;}
if(copySharkMap[y][x].size>0){
if(copySharkMap[y][x].size>size) continue;
copySharkMap[y][x].size=size;
copySharkMap[y][x].dir=dir;
copySharkMap[y][x].speed=speed;
}else{
copySharkMap[y][x].size=size;
copySharkMap[y][x].dir=dir;
copySharkMap[y][x].speed=speed;
}
}
}
}
for(int i=0;i<N;i++){
for(int s=0;s<M;s++){
sharkMap[i][s]=copySharkMap[i][s];
}
}
}
void solve(){
int score=0;
for(int i=0;i<M;i++){
score+=getShark(i);
//cout<<score<<"\n";
moveShark();
//printSharK();
}
cout<<score<<"\n";
}
(내가 생각하기엔 이 코드에서 일반 배열을 사용했다면 디버깅은 편했을 것 같았으나 매번 상어의 위치를 찾을 때마다 Map전체를 계속 탐색해야 되기에 시간은 좀 더 늘어났을 것이다.)
