🧩 문제
▶ 백준 17143 낚시왕 바로가기
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.
낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
- 낚시왕이 오른쪽으로 한 칸 이동한다.
- 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
- 상어가 이동한다.
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.
상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.
입력
첫째 줄에 격자판의 크기 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) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.
출력
낚시왕이 잡은 상어 크기의 합을 출력한다.
예제
입력
4 6 8
4 1 3 3 8
1 3 5 2 9
2 4 8 4 1
4 5 0 1 4
3 3 1 2 7
1 5 8 4 3
3 6 2 1 2
2 2 2 3 5출력
22각 칸의 왼쪽 아래에 적힌 수는 속력, 오른쪽 아래는 크기, 왼쪽 위는 상어를 구분하기 위한 문자이다. 오른쪽 위에 ❤️는 낚시왕이 잡은 물고기 표시이다.
초기 상태
1초
2초 (E번 상어는 B번에게 먹혔다)
3초
4초
5초
6초
🎯 풀이
| 메모리 | 시간 | 코드길이 |
|---|---|---|
| 48180 KB | 632 ms | 5315 B |
Point
- 상어는 동시에 움직여야 한다.
- 상어가 각자의 속력으로 이동할 때 한칸씩 이동시키면 시간초과가 발생하므로(0 ≤ 속력 ≤ 1000)
나누기 연산을 사용하여 이동시키는데에 있어서 최적화 시킨다.
1. 상어 클래스
private static class Shark {
int speed, direction, size;
public Shark(int speed, int direction, int size) {
this.speed = speed;
this.direction = direction;
this.size = size;
}
}각 상어의 속력, 방향, 크기를 가지고 있는 상어 클래스를 만든다. 이 상어 클래스는 이차원 배열에 들어가있으므로 따로 행값과 열값을 가지고 있지는 않다.
2. 이차원 배열 설정과 방향 배열 설정
R = Integer.parseInt(st.nextToken()) + 1; //map을 1부터 사용하기 위해서
C = Integer.parseInt(st.nextToken()) + 1;입력받은 map의 크기보다 행, 열값을 하나씩 더 크게 해준다. 입력받는 상어의 위치가 1부터 시작하기 때문이다.
private static int [][] d = {{0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};방향 또한 1부터 시작하므로 사용하진 않지만 index 0 값에 {0,0}을 추가해주었다.
3. 낚시꾼의 이동 & 낚시
for(int fisher = 1; fisher < C; fisher++) {
for(int deep = 1; deep < R; deep++) {
if(sharks[deep][fisher] != null) {
cnt += sharks[deep][fisher].size;
sharks[deep][fisher] = null; //잡음 처리
break;
}
}
/*
상어이동 코드
*/
}낚시꾼은 1부터 오른쪽으로 한 칸씩 움직이면서 자신과 가장 가까운 상어를 잡는다. 한 열에서 한 마리의 상어만 잡을 수 있으므로 해당 열에서 상어를 잡는다면 낚시는 끝난다.
4. 상어의 이동
상어는 동시에 이동해야하기 때문에 기존의 sharks 이차원 배열에서 이동시키면 안된다. 따라서 같은 사이즈를 갖는 sharksTmp 배열을 만들었다. sharks에 있던 상어들은 이동 후에 sharksTmp에 저장된다.
상어들은 각자의 스피드와 방향으로 이동한다. 이때, 속력의 최대값은 1000이기 때문에 상어를 한 칸씩 이동시키면 시간초과가 발생한다. 이를 최적화 시켜주기 위해 나누기 연산을 사용하였다.
원래의 위치로 돌아오기 위해 거쳐야하는 칸 수는 2R-2 칸임을 알 수 있다. 나는 R 대신 R-1을 사용하였으므로 R대신 R-1을 사용하였다. 따라서 상어의 속력을 2(R-1)*2로 나누면 몫은 해당 행을 몇바퀴 돌았는지, 나머지는 그 이후에 몇 칸을 더 갔는지로 나타난다. 몇 칸을 더 갔는지만 알면 되므로 나누기 연산(%)을 사용하였다.
이 속력을 토대로 한 칸씩 이동시켜주었다. 이동을 시키는 도중 맵 밖을 벗어난다면 방향을 바꿔주고 다시 원래 자리로 간 후, 원래 이동했어야했던 방향으로 한번 더 이동시켜 주었다.
//이동해야하는 거리만큼 이동시켜주기
for(int s = 0; s < speed; s++) {
nr += d[direction][0];
nc += d[direction][1];
//맵안에 있지 않다면
if(!isIn(nr, nc)) {
direction = changeDirection(direction); //방향 바꿔주기
nr += d[direction][0] * 2; //이동한 것 다시 되돌려주고 이동해야했던 것 이동
nc += d[direction][1] * 2;
}
}다음으로 이동 후 상태를 저장하는 sharkTmp에 이동한 상어를 저장시키는데, 이때 같은 위치에 다른 상어가 있다면 둘의 사이즈를 비교하여 더 큰 상어를 넣는다.
//임시 map에 상어 저장해주기
//a. 해당 위치에 다른 상어가 있다면 사이즈 비교해서 더 큰 애로 넣기
if(sharksTmp[nr][nc] != null) {
if(sharksTmp[nr][nc].size < size) {
sharksTmp[nr][nc] = new Shark(speed, direction, size);
}
}
//b. 아무것도 없다면 그냥 상어 넣어도 됨.
else {
sharksTmp[nr][nc] = new Shark(speed, direction, size);
}이동 후의 상어들이 모두 sharksTmp에 저장되었다면 원래의 sharks 배열로 깊은 복사를 한다.
낚시꾼이 한 칸씩 이동할 때마다 4. 상어의 이동을 반복해주면 답을 도출해낼 수 있다.
⭐️ 전체 풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ17143_낚시왕 {
private static int R, C;
private static Shark[][] sharks, sharksTmp;
private static int [][] d = {{0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
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()) + 1; //map을 1부터 사용하기 위해서
C = Integer.parseInt(st.nextToken()) + 1;
int M = Integer.parseInt(st.nextToken()); //상어의 수
int cnt = 0; //낚시왕이 잡은 상어의 수
sharks = new Shark[R][C];
//M개의 상어 정보
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 speed = Integer.parseInt(st.nextToken());
int direction = Integer.parseInt(st.nextToken()); //1: 위, 2: 아래, 3: 오른쪽, 4: 왼쪽
int size = Integer.parseInt(st.nextToken());
sharks[r][c] = new Shark(speed, direction, size);
}
//낚시왕 활동 시작!
for(int fisher = 1; fisher < C; fisher++) {
//2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
for(int deep = 1; deep < R; deep++) {
if(sharks[deep][fisher] != null) {
cnt += sharks[deep][fisher].size;
sharks[deep][fisher] = null; //잡음 처리
break;
}
}
//상어가 동시에 이동하는 것을 구현하기 위한 배열
//낚시왕이 한번 이동할때마다 초기화 됨
sharksTmp = new Shark[R][C];
//3. 상어가 이동한다.
for(int r = 1; r < R; r++) {
for(int c = 1; c < C; c++) {
if(sharks[r][c] != null) {
int direction = sharks[r][c].direction;
int speed = sharks[r][c].speed;
int size = sharks[r][c].size;
int nr = r; //이동 후 행
int nc = c; //이동 후 열
//a. 상어가 위아래로 이동
if(direction == 1 || direction == 2) {
speed %= 2*(R-1) - 2;
}
//b. 상어가 좌우로 이동
else {
speed %= 2*(C-1) - 2;
}
//이동해야하는 거리만큼 이동시켜주기
for(int s = 0; s < speed; s++) {
nr += d[direction][0];
nc += d[direction][1];
//맵안에 있지 않다면
if(!isIn(nr, nc)) {
direction = changeDirection(direction); //방향 바꿔주기
nr += d[direction][0] * 2; //이동한 것 다시 되돌려주고 이동해야했던 것 이동
nc += d[direction][1] * 2;
}
}
//임시 map에 상어 저장해주기
//a. 해당 위치에 다른 상어가 있다면 사이즈 비교해서 더 큰 애로 넣기
if(sharksTmp[nr][nc] != null) {
if(sharksTmp[nr][nc].size < size) {
sharksTmp[nr][nc] = new Shark(speed, direction, size);
}
}
//b. 아무것도 없다면 그냥 상어 넣어도 됨.
else {
sharksTmp[nr][nc] = new Shark(speed, direction, size);
}
}
}
}
//sharkTmp에 있던 상어들을 shark로 복사시키자
for(int i = 1; i < R; i++) {
for(int j = 1; j < C; j++) {
Shark tmp = sharksTmp[i][j];
sharks[i][j] = tmp;
}
}
}
System.out.println(cnt);
} //main 끝
private static boolean isIn(int r, int c) {
if(r > 0 && c > 0 && r < R && c < C)
return true;
else
return false;
}
private static int changeDirection(int d) {
switch (d) {
case 1:
return 2;
case 2:
return 1;
case 3:
return 4;
case 4:
return 3;
default:
return -1;
}
}
private static class Shark {
int speed, direction, size;
public Shark(int speed, int direction, int size) {
this.speed = speed;
this.direction = direction;
this.size = size;
}
}
}
느낀 점
22년 10월 경에 시도했던 문제지만 결국 풀지 못했고 2달이 지난 22년 12월 오늘 다시 도전하였다. 그 때는 시간초과가 났었는데, 수식을 이용하여 반복작업을 줄일 생각을 하지 못했다. 조건을 확인하고 for문의 반복작업을 줄이는 연습을 해야할 것 같다.
또한, 첫 velog 게시물을 작성하면서 "남들이 내 코드를 보았을 때 쉽게 이해할 수 있을까?"라는 생각이 계속 들었다. 꾸준한 게시글과 연습을 통해서 발전해야겠다.
