17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
낚시왕은 1번 열부터 N번 열까지 1초에 한칸씩 움직이며 차례대로 낚시를 합니다.
1초동안 일어나는 일은
1. 낚시왕이 오른쪽으로 한 칸 이동합니다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡습니다.
3. 상어가 이동합니다.
상어에 대한 정보는 좌표(x, y), 속력(s), 이동 방향(d), 크기(z)가 주어지며, 이동 방향에 맞춰서 속력만큼 이동합니다.
이동 중에 맵 밖으로 나가려고 하는 경우에는 방향을 반대로 바꿔준 후에 그대로 이동합니다.
상어가 이동을 마쳤을 때 같은 칸에 여러마리의 상어가 있을 수 있는데 이 경우에는 크기가 가장 큰 상어만 살아남습니다.
이 조건들을 모두 고려하여 시뮬레이션을 돌렸을 때 낚시왕이 잡은 상어의 크기 합을 구하는 문제입니다.
저는 두가지 방법으로 해결해보았습니다.
1. 배열의 모든 칸을 클래스화해서 관리하는 방법
2. 배열에는 상어의 번호만 유지하는 방법
먼저 첫 번째 방법입니다.
저는 모든 칸을 클래스화해서 관리하였습니다. (속력, 방향, 크기)
상어가 없는 칸은 (0, 0, 0)이 채워져있을 것이고, 상어가 있는 칸은 (speed, d, size)가 채워져 있습니다.
먼저 낚시왕이 상어를 잡고, 상어를 이동시켜줍니다.
이동을 완료한 상어들이 같은 좌표에 있으면 제거를 해야하기 때문에 상어들의 새로운 위치를 구별해주기 위한 새로운 배열(tmp)을 사용하였습니다.
우선 속력만큼 이동을 모두 시켜준다면 시간초과가 뜰것 같아서 mod를 사용하였습니다.
상어가 가로로 이동 중이라면 %((M - 1) * 2), 세로로 이동 중이라면 %((N - 1) * 2)만큼만 이동하였습니다.
tmp[nx][ny].size가 0이면 상어가 없으므로 상어를 넣어줍니다.
tmp[nx][ny].size가 0이 아니면 이미 다른 상어가 도착한 상태이므로 크기가 큰 상어로 갱신합니다.
이 과정을 낚시왕이 맵밖으로 나갈때까지 반복한 후에 크기 합을 출력해줍니다.
두 번째 방법입니다.
shark라는 클래스 배열을 이용하여 상어들의 정보를 담아놓습니다. (번호, 좌표(x, y), 속력, 방향, 크기, 죽었는지 여부)
그리고 list배열에는 각 칸에 들어있는 상어의 번호를 저장합니다. (상어가 없으면 0)
로직은 첫 번째 방법과 같지만 다른 점은
1번 방법은 N * M을 돌면서 상어가 있는 칸에만 이동을 시키고, 상어의 모든 정보를 이동시켜야하므로 새로운 클래스배열을 선언하였지만
2번 방법은 상어의 수만큼만 반복하면 되고, 인덱스만 이동시키면 되기때문에 새로운 int배열을 선언하였다는 차이입니다.
시간은 비슷하지만 1번 방법의 메모리가 2번에 비해 엄청 많이 차지하였습니다.
그리고 상어를 움직일 때 mod를 사용하지 않고 돌려보니 시간 차이가 많이 나는것을 알 수 있습니다.
[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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static class Pair {
int speed;
int d;
int size;
public Pair(int speed, int d, int size) {
this.speed = speed;
this.d = d;
this.size = size;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<Pair> shark = new ArrayList<>();
static Pair list[][] = new Pair[101][101];
static int direct[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
static int N, M, sharkCnt, ans;
static Pair[][] moveShark() {
Pair tmp[][] = new Pair[101][101];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
tmp[i][j] = new Pair(0, 0, 0);
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (list[i][j].size > 0) {
int dis = list[i][j].speed;
int d = list[i][j].d;
int size = list[i][j].size;
if (d > 1)
dis %= ((M - 1) * 2);
else
dis %= ((N - 1) * 2);
int nx = i;
int ny = j;
for (int k = 0; k < dis; k++) {
if (nx == 1 && d == 0)
d = 1;
else if (nx == N && d == 1)
d = 0;
else if (ny == 1 && d == 3)
d = 2;
else if (ny == M && d == 2)
d = 3;
nx += direct[d][0];
ny += direct[d][1];
}
if (tmp[nx][ny].size == 0) {
tmp[nx][ny].speed = list[i][j].speed;
tmp[nx][ny].d = d;
tmp[nx][ny].size = size;
} else {
if (tmp[nx][ny].size < size) {
tmp[nx][ny].speed = list[i][j].speed;
tmp[nx][ny].d = d;
tmp[nx][ny].size = size;
}
}
}
}
}
return tmp;
}
static void func() {
for (int j = 1; j <= M; j++) {
for (int i = 1; i <= N; i++) {
if (list[i][j].size > 0) {
ans += list[i][j].size;
list[i][j].speed = 0;
list[i][j].d = 0;
list[i][j].size = 0;
break;
}
}
if (j == M)
break;
list = moveShark();
}
System.out.println(ans);
}
static void init() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
list[i][j] = new Pair(0, 0, 0);
}
}
static void input() throws Exception {
int x, y, s, d, z;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
sharkCnt = Integer.parseInt(st.nextToken());
init();
for (int i = 0; i < sharkCnt; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
z = Integer.parseInt(st.nextToken());
list[x][y].speed = s;
list[x][y].d = d - 1;
list[x][y].size = z;
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
[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
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static class Pair {
int idx;
int x;
int y;
int speed;
int d;
int size;
boolean die;
public Pair(int idx, int x, int y, int speed, int d, int size) {
this.idx = idx;
this.x = x;
this.y = y;
this.speed = speed;
this.d = d;
this.size = size;
this.die = false;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int newlist[][] = new int[101][101];
static int list[][] = new int[101][101];
static Pair shark[] = new Pair[10001];
static int direct[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
static int N, M, sharkCnt, ans;
static void moveShark() {
for (int i = 1; i <= N; i++)
Arrays.fill(newlist[i], 0);
for (int i = 1; i <= sharkCnt; i++) {
int x = shark[i].x;
int y = shark[i].y;
int speed = shark[i].speed;
int d = shark[i].d;
int size = shark[i].size;
boolean die = shark[i].die;
if (die)
continue;
if (d > 1)
speed %= ((M - 1) * 2);
else
speed %= ((N - 1) * 2);
int nx = x;
int ny = y;
for (int k = 0; k < speed; k++) {
if (nx == 1 && d == 0)
d = 1;
else if (nx == N && d == 1)
d = 0;
else if (ny == 1 && d == 3)
d = 2;
else if (ny == M && d == 2)
d = 3;
nx += direct[d][0];
ny += direct[d][1];
}
shark[i].d = d;
if (newlist[nx][ny] == 0) {
newlist[nx][ny] = i;
shark[i].x = nx;
shark[i].y = ny;
} else {
int idx = newlist[nx][ny];
int presize = shark[idx].size;
if (presize < size) {
shark[idx].die = true;
newlist[nx][ny] = i;
shark[i].x = nx;
shark[i].y = ny;
} else {
shark[i].die = true;
}
}
}
}
static void func() {
for (int j = 1; j <= M; j++) {
for (int i = 1; i <= N; i++) {
if (list[i][j] > 0) {
int idx = list[i][j];
ans += shark[idx].size;
shark[idx].die = true;
list[i][j] = 0;
break;
}
}
if (j == M)
break;
moveShark();
for (int x = 1; x <= N; x++)
for (int y = 1; y <= M; y++)
list[x][y] = newlist[x][y];
}
System.out.println(ans);
}
static void input() throws Exception {
int x, y, s, d, z;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
sharkCnt = Integer.parseInt(st.nextToken());
for (int i = 1; i <= sharkCnt; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
z = Integer.parseInt(st.nextToken());
shark[i] = new Pair(i, x, y, s, d - 1, z);
list[x][y] = i;
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > Implementation' 카테고리의 다른 글
| boj 20207 달력 (0) | 2021.04.22 |
|---|---|
| boj 17144 미세먼지 안녕! (0) | 2021.04.14 |
| boj 2564 경비원 (0) | 2021.04.13 |
| boj 16719 ZOAC (0) | 2021.03.15 |
| boj 3085 사탕 게임 (0) | 2021.02.26 |