문제
R x C 격자에 M마리의 상어가 있다. 낚시왕이 왼쪽부터 오른쪽으로 이동하며, 매 열에서 가장 가까운 상어를 잡는다. 이후 상어들이 속도와 방향에 따라 이동하고, 같은 칸의 상어 중 가장 큰 것만 남는다.
입력
첫째 줄에 R, C, M이 주어진다. 이후 M줄에 각 상어의 위치(r, c), 속력(s), 방향(d), 크기(z)가 주어진다.
출력
낚시왕이 잡은 상어 크기의 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 6 8 4 1 3 3 8 ... (생략) | 22 |
풀이
낚시, 상어 이동, 겹침 처리를 C번(열 수만큼) 반복 시뮬레이션한다.
- 낚시: 현재 열에서 가장 위에 있는 상어를 잡고 리스트에서 제거한다
- 이동: 각 상어가 속력만큼 한 칸씩 이동하되, 벽에 부딪히면 방향을 반전한다
- 겹침 처리: 이동 후 같은 칸에 여러 상어가 있으면, 가장 큰 상어만 남기고 나머지를 제거한다
- map 배열로 각 칸의 상어 크기를 추적한다
핵심 아이디어: 상어 이동 시 벽 반사를 한 칸씩 처리하고, equals를 크기(z)로 오버라이드하여 리스트에서 특정 크기의 상어를 제거한다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day452BOJ17143낚시왕 {
static int R, C, M;
static int answer = 0;
static int[][] map;
static int[][] deltas = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
static StringTokenizer st;
static List<Shark> list = new ArrayList<>();
static class Shark {
int r, c, s, d, z;
public Shark(int z) {
super();
this.z = z;
}
public Shark(int r, int c, int s, int d, int z) {
super();
this.r = r;
this.c = c;
this.s = s;
this.d = d;
this.z = z;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Shark other = (Shark) obj;
if (z != other.z)
return false;
return true;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[R + 1][C + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken()) - 1;
int z = Integer.parseInt(st.nextToken());
map[r][c] = z;
list.add(new Shark(r, c, s, d, z));
}
for (int i = 1; i <= C; i++) {
fishing(i);
swimming();
map = setUp();
}
System.out.println(answer);
}
static void fishing(int c) {
for (int i = 1; i <= R; i++) {
if (map[i][c] > 0) {
answer += map[i][c];
list.remove(new Shark(map[i][c]));
map[i][c] = 0;
return;
}
}
}
static void swimming() {
for (int i = 0; i < list.size(); i++) {
Shark temp = list.get(i);
for (int j = 0; j < temp.s; j++) {
int nr = temp.r + deltas[temp.d][0];
int nc = temp.c + deltas[temp.d][1];
if (isIn(nr, nc)) {
temp.r = nr;
temp.c = nc;
} else {
if (temp.d % 2 == 0)
temp.d++;
else
temp.d--;
j--;
}
}
}
}
static int[][] setUp() {
int[][] tempMap = new int[R + 1][C + 1];
for (int i = 0; i < list.size(); i++) {
Shark temp = list.get(i);
if (tempMap[temp.r][temp.c] == 0) {
tempMap[temp.r][temp.c] = temp.z;
} else {
if (tempMap[temp.r][temp.c] < temp.z) {
list.remove(new Shark(tempMap[temp.r][temp.c]));
tempMap[temp.r][temp.c] = temp.z;
} else {
list.remove(new Shark(temp.z));
}
i--;
}
}
return tempMap;
}
static boolean isIn(int r, int c) {
return r > 0 && r < R + 1 && c > 0 && c < C + 1;
}
}복잡도
- 시간: O(C * M * S) (S: 최대 속력, 벽 반사 한 칸씩 처리)
- 공간: O(R * C + M)