728x90
17143 - 낚시왕
https://www.acmicpc.net/problem/17143


문제
RxC인 격자판에서 낚시왕이 상어 낚시/ 격자판의 각 칸은 (r, c)로 나타낼 수 있는데 r은 행, c는 열이고 (R, C)는 가장 오른쪽 아래
칸에는 상어가 최대 1마리 들어있을 수 있고 상어는 크기와 속도를 가지고 있음
낚시왕은 처음에 1번 열의 한 칸 위에 있음
1초 동안 순서대로 일어나며, 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동 멈춤
1. 낚시왕 오른쪽으로 한 칸 이동
2. 낚시왕이 있는 열에 있는 상어 중 땅과 제일 가까운 상어 잡음/ 상어 잡으면 격자판에서 사라짐
3. 상어 이동
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초
상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우 방향을 반대로 바꿔 속력 유지한채로 이동
상어가 이동 마친 후에 한 칸에 상어가 2마리 이상 있을 수 있고, 크기가 가장 큰 상어가 나머지 상어 모두 잡아먹음
입력
첫째 줄: 격자판의 크기 R, C, 상어 수 M (2 <= R, C <= 100, 0 <= M <= R*C)
둘째 줄 ~ M개 줄: 상어의 정보인 위치 r, c, 속력 s, 이동 방향 d, 크기 z
(1 <= r <= R, 1 <= c <= C, 0 <= s <= 1000, 1 <= d <= 4, 1 <= z <= 10000)
(d가 1: 위/ 2: 아래/ 3: 오른쪽/ 4: 왼쪽)
출력: 낚시왕이 잡은 상어 크기의 합
풀이
Shark 클래스
- r, c: 위치 (0-index)
- s: 속력 (이동 칸 수)
- d: 방향 (1: 위/ 2: 아래/ 3: 오른쪽/ 4: 왼쪽)
- `int[] dr = {0, -1, 1, 0, 0}`
- `int[] dc = {0, 0, 0, 1, -1}`
- ex. 위: dr[1] = -1, dc[1] = 1 -> (r - 1, c)
- z: 크기 (잡거나 충돌 시 비교 기준)
static class Shark {
int r, c, s, d, z;
Shark(int r, int c, int s, int d, int z) {
this.r = r;
this.c = c;
this.s = s;
this.d = d;
this.z = z;
}
}
`catchShark(col)`: 해당 열에서 상어 잡기
- `col` 열에 있는 상어 중 r이 가장 작은(가장 위) 상어 찾음
- O -> 상어를 리스트에서 제거, 크기 z `return`
static int catchShark(int col) {
Shark target = null;
int minRow = R;
for (Shark s : sharks) {
if (s.c == col && s.r < minRow) {
minRow = s.r;
target = s;
}
}
if (target != null) {
sharks.remove(target);
return target.z;
}
return 0;
}
`moveSharks()`: 모든 상어 이동 + 충돌 처리
- 상어 벽에 부딪히면 방향 반대로 바꾸며 왕복
- 세로: `s.d == 1 || s.d == 2` -> `(R - 1) * 2`
- 가로: `(C - 1) * 2`
- 1칸씩 이동하면서 벽이면 방향 반전
- 같은 칸에 여러 마리 -> 큰 상어만 남김
- `Map<Intger, Shark> HM = new HashMap<>()`: 칸 하나당 상어 하나
- `key = s.r * C + s.c`: 2차원 좌표 (r, c) -> 1차원 정수로 바꿈
- 2차원 배열의 1차원 인덱싱: `index = row * width + col`
- `!HM.containsKey(key) || HM.get(key).z < s.z`: 칸에 아직 상어 X or 이미 있는 상어보다 지금 상어가 큼
-> `HM.put(key, s)`: 지금 상어로 교체
static List<Shark> moveSharks() {
Map<Integer, Shark> HM = new HashMap<>();
for (Shark s : sharks) {
int move = s.s;
if (s.d == 1 || s.d == 2) move %= (R - 1) * 2;
else move %= (C - 1) * 2;
for (int i = 0; i < move; i++) {
int nr = s.r + dr[s.d];
int nc = s.c + dc[s.d];
if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
if (s.d == 1) s.d = 2;
else if (s.d == 2) s.d = 1;
else if (s.d == 3) s.d = 4;
else if (s.d == 4) s.d = 3;
nr = s.r + dr[s.d];
nc = s.c + dc[s.d];
}
s.r = nr;
s.c = nc;
}
int key = s.r * C + s.c;
if (!HM.containsKey(key) || HM.get(key).z < s.z) {
HM.put(key, s);
}
}
return new ArrayList<>(HM.values());
}
코드
import java.io.*;
import java.util.*;
// 낚시왕
public class boj_17143 {
static class Shark {
int r, c, s, d, z;
Shark(int r, int c, int s, int d, int z) {
this.r = r;
this.c = c;
this.s = s;
this.d = d;
this.z = z;
}
}
static int R, C, M;
static int[] dr = {0, -1, 1, 0, 0};
static int[] dc = {0, 0, 0, 1, -1};
static List<Shark> sharks;
static int catchShark(int col) {
Shark target = null;
int minRow = R;
for (Shark s : sharks) {
if (s.c == col && s.r < minRow) {
minRow = s.r;
target = s;
}
}
if (target != null) {
sharks.remove(target);
return target.z;
}
return 0;
}
static List<Shark> moveSharks() {
Map<Integer, Shark> HM = new HashMap<>();
for (Shark s : sharks) {
int move = s.s;
if (s.d == 1 || s.d == 2) move %= (R - 1) * 2;
else move %= (C - 1) * 2;
for (int i = 0; i < move; i++) {
int nr = s.r + dr[s.d];
int nc = s.c + dc[s.d];
if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
if (s.d == 1) s.d = 2;
else if (s.d == 2) s.d = 1;
else if (s.d == 3) s.d = 4;
else if (s.d == 4) s.d = 3;
nr = s.r + dr[s.d];
nc = s.c + dc[s.d];
}
s.r = nr;
s.c = nc;
}
int key = s.r * C + s.c;
if (!HM.containsKey(key) || HM.get(key).z < s.z) {
HM.put(key, s);
}
}
return new ArrayList<>(HM.values());
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
sharks = new ArrayList<>();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
sharks.add(new Shark(r, c, s, d, z));
}
int ans = 0;
for (int col = 0; col < C; col++) {
ans += catchShark(col);
sharks = moveSharks();
}
System.out.println(ans);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/BFS] 백준 16946 - 벽 부수고 이동하기 4 (Java) (0) | 2026.01.12 |
|---|---|
| [BOJ/DP] 백준 2342 - Dance Dance Revolution (Java) (0) | 2026.01.12 |
| [BOJ/BFS] 백준 2146 - 다리 만들기 (Java) (0) | 2026.01.05 |
| [BOJ/Segment Tree] 백준 11505 - 구간 곱 구하기 (Java) (0) | 2025.12.24 |
| [BOJ/DP] 백준 11066 - 파일 합치기 (Java) (0) | 2025.12.22 |