[BOJ] 17143 - 낚시왕
📌 문제 정보
- 문제 번호: BOJ 17143
- 문제 이름: 낚시왕
- 난이도: Gold
- 분류: 구현
🧩 문제 요약
- 주어지는 입력
R = 격자판 행 길이
C = 격자판 열 길이
M = 상어의 수
둘째 줄부터 M개의 줄에 상어의 정보가 주어짐
R = 상어의 행 위치
C = 상어의 열 위치
S = 상어의 속력
D = 상어의 이동 방향
Z = 상어의 크기- 무엇을 구해야 하는지
낚시왕이 잡은 상어 크기의 합을 출력함.
동작은 다음과 같음
1. 낚시왕이 오른쪽으로 1칸 움직임
2. 낚시왕과 같은 열에서 가장 가까운 상어를 잡음
3. 상어가 이동함
4. 낚시왕이 격자판을 벗어날 때까지 1~3을 반복함.💡 접근 아이디어
- 처음 떠올린 방법
상어의 정보를 담는 이차원 배열을 생성하여 시뮬레이션을 생각했습니다.
가장 생각을 많이 한 부분은 상어의 좌표 이동 방식이었습니다.
오랜 시간동안 고민한 결과 배열을 확장해서 상어의 이동 구현을 성공했습니다.
🛠️ 해결 전략
구현 흐름을 단계별로 정리합니다.
- 상태 정의
가장 먼저 든 생각은 우선순위 큐이다.
해당 칸에 여러 상어가 존재할 때 가장 큰 상어만 존재한다고 했을 때
크기 순으로 정렬한 다음 작은 상어부터 움직이면
큰 상어만 남게 되겠구나 생각을 했다.- 핵심 로직(점화식 / 이동 규칙)
좌표 이동을 도울 가로 배열과 세로 배열을 생성한다.
이때 크기는 전체 행 크기 * 2 - 2이다.
이렇게 정한 이유는 상어가 좌우 혹은 상하로 움직일 때
끝점에서 끝점으로 왕복하면 끝점에서는 방문을 1번만 하고
나머지 좌표에선 2번씩 방문하기 때문이다.
그런 다음 배열에 숫자를 입력한다.
0부터 행의 최대 길이까지는 좌표를 증가하여 입력하고
그 다음 끝까지는 좌표를 감소하여 입력한다.
2.
만약 상어의 좌표가 감소하는 방향이면 배열의 최대 길이에서 현재 좌표를 빼고 순회한다.⚠️ 주의할 점
풀이 중 헷갈리거나 실수하기 쉬운 부분입니다.
- 상어의 좌표 이동
가장 이 문제에서 어려운 부분이라고 생각한다.
상어가 배열 밖으로 나갈 때마다 방향 전환을 하면 시간이 더 오래걸릴 것 같아서 최선의 방법을 찾으려 시간이 오래 걸렸었는데 우선은 일단 구현을 해볼걸이라는 생각이 든다.
배열 밖으로 벗어나는 경우 반대로 이동이라는 조건만 추가되었는데도 생각하는데 오래걸렸다.✅ 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static class Shark implements Comparable<Shark> {
int r; // 행 위치
int c; // 열 위치
int s; // 상어 속력
int d; // 상어 방향
int z; // 상어 사이즈
public 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;
}
// 상어를 사이즈 순으로 비교
@Override
public int compareTo(Shark o) {
return Integer.compare(this.z, o.z);
}
}
static int ans = 0, r, c, m;
static Shark [][] map;
static int [] rows;
static int [] cols;
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());
putArr();
map = new Shark [r][c];
for (int i=0;i<m;i++) {
st = new StringTokenizer(br.readLine());
int sharkR = Integer.parseInt(st.nextToken())-1;
int sharkC = Integer.parseInt(st.nextToken())-1;
int sharkS = Integer.parseInt(st.nextToken());
int sharkD = Integer.parseInt(st.nextToken());
int sharkZ = Integer.parseInt(st.nextToken());
map[sharkR][sharkC] = new Shark(sharkR,sharkC,sharkS,sharkD,sharkZ);
}
PriorityQueue<Shark> pq = new PriorityQueue<>();
for (int i=0;i<c;i++) {
getShark(i);
findShark(pq);
moveShark(pq);
}
System.out.println(ans);
}
// 좌표 이동을 돕는 배열 초기화
private static void putArr() {
rows = new int[r * 2 - 2];
cols = new int[c * 2 - 2];
int len = -1;
for (int i = 0; i < r; i++) rows[i] = ++len;
for (int i = r; i < r * 2 - 2; i++) rows[i] = --len;
len = -1;
for (int i = 0; i < c; i++) cols[i] = ++len;
for (int i = c; i < c * 2 - 2; i++) cols[i] = --len;
}
// 상어가 좌표 이동하는 함수
private static void moveShark(PriorityQueue<Shark> pq) {
while (!pq.isEmpty()) {
Shark s = pq.poll();
if (s.d <= 2)
moveV(s);
else
moveH(s);
map[s.r][s.c] = s;
}
}
// 상어가 가로축 이동하는 함수
// 3 = 오른쪽(증가), 4 = 왼쪽(감소)
private static void moveH(Shark s) {
if (c == 1) {
s.c = 0;
return ;
}
int len = c * 2 - 2;
int nextC = s.c;
// 만약 이동 방향이 감소하는 방향이라면
if (s.d == 4)
nextC = len - s.c;
nextC += s.s;
nextC %= len;
if (nextC < c)
s.d = 3;
else
s.d = 4;
s.c = cols[nextC];
}
// 상어가 세로축 이동하는 함수
// 1 = 위쪽(감소), 2 = 아래쪽(증가)
private static void moveV(Shark s) {
if (r == 1) {
s.r = 0;
return ;
}
int len = r * 2 - 2;
int nextR = s.r;
// 만약 이동 방향이 감소하는 방향이라면
if (s.d == 1)
nextR = len - s.r;
nextR += s.s;
nextR %= len;
if (nextR < r)
s.d = 2;
else
s.d = 1;
s.r = rows[nextR];
}
// 상어를 찾는 함수
private static void findShark(PriorityQueue<Shark> pq) {
for (int i=0;i<r;i++) {
for (int j=0;j<c;j++) {
if (map[i][j] != null) {
pq.add(map[i][j]);
map[i][j] = null;
}
}
}
}
// 어부가 상어를 잡는 함수
private static void getShark(int idx) {
for (int i=0;i<r;i++) {
if (map[i][idx] != null) {
ans += map[i][idx].z;
map[i][idx] = null;
break;
}
}
}
}
돈 많이 벌래