백준 17143 - 낚시왕
Updated:
Java
17143 번 - 낚시왕
문제
- 낚시왕이 오른쪽으로 한 칸 이동한다.
- 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
- 상어가 이동한다.
낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.
접근 방법
상어의 정보를 배열로 저장하되, 상어가 살아있는지 죽었는 지에 대한 정보를 저장하였다.
낚시꾼을 움직이다가 상어를 발견하면, 상어를 잡고 상어의 배열 첫번째 값을 -1로 하여 죽었다고 표시한다.
이후 살아있고, 아직 움직이지 않은 상어들을 하나씩 이동시킨다.
상어를 움직이다, 다른 상어를 만났을 때,
아직 움직이지 않은 상어는 이동시키고, 아니면 크기를 비교하여 둘 중 하나의 상어는 죽인다.
상어가 이동하였는지 아닌지는 따로 boolean 배열로 표시를 한다.
시간을 단축 시키기 위해, 이동하는 거리를 ([세로 or 가로길이] - 1) * 2로 modulo 처리 해준다.
왜냐하면 한 바퀴 돌고나면 결국 그 자리에 그 방향으로 돌아오기 때문이다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, sharkNum, result;
static ArrayList<int[]> shark;
static int[][] map;
static boolean[] moved;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = stoi(stk.nextToken());
m = stoi(stk.nextToken());
sharkNum = stoi(stk.nextToken());
map = new int[n][m];
shark = new ArrayList<>();
shark.add(new int[] {});
moved = new boolean[sharkNum + 1]; // 각 상어가 움직였는지 확인하는 배열
// (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기
int r, c, s, d, z;
for(int i = 1; i <= sharkNum; i++) {
stk = new StringTokenizer(br.readLine());
r = stoi(stk.nextToken()) - 1;
c = stoi(stk.nextToken()) - 1;
s = stoi(stk.nextToken());
d = stoi(stk.nextToken());
z = stoi(stk.nextToken());
map[r][c] = i;
shark.add(new int[] {1, r, c, s, d, z});
}
int angler = 0;
while(angler < m) {
// 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
for(int i = 0; i < n; i++) {
if(map[i][angler] != 0) {
shark.get(map[i][angler])[0] = -1;
result += shark.get(map[i][angler])[5];
map[i][angler] = 0;
break;
}
}
Arrays.fill(moved, false);
// 상어가 이동한다.
for(int i = 1; i <= sharkNum; i++) {
// 죽은 상어거나, 이미 움직인 상어라면
if(shark.get(i)[0] == -1 || moved[i])
continue;
move(shark.get(i), i);
}
// 낚시왕이 오른쪽으로 한 칸 이동한다.
angler++;
}
System.out.println(result);
br.close();
}
// 위 아래 오른쪽 왼쪽
static int dy[] = {0,-1,1,0,0};
static int dx[] = {0,0,0,1,-1};
static int revesed[] = {0,2,1,4,3}; // 반대 방향
// 상어를 움직인다.
private static void move(int[] is, int idx) {
int y = is[1], x = is[2], s = is[3], d = is[4], z = is[5];
int ny = y,nx = x;
// 벽에 부딛히는 경우, 결국 제자리로 돌아오므로 횟수를 줄여준다
if(d == 1 || d == 2)
s = s % ((n - 1) * 2);
else
s = s % ((m - 1) * 2);
// 상어를 한 칸씩 이동시킨다.
for(int i = 0; i < s; i++) {
ny += dy[d];
nx += dx[d];
// 만약 map 범위를 벗어나면 방향을 바꾼다.
if(!isIn(ny,nx)) {
d = revesed[d];
ny += dy[d] * 2;
nx += dx[d] * 2;
}
}
// 상어 위치 갱신
shark.get(idx)[1] = ny;
shark.get(idx)[2] = nx;
shark.get(idx)[4] = d;
map[y][x] = 0;
moved[idx] = true;
// 만약 도착한 자리에 다른 상어가 있으면??
if(map[ny][nx] != 0) {
// 도착한 위치의 이미 존재하는 상어가 아직 출발 안했을 수도 있음
if(!moved[map[ny][nx]]) {
move(shark.get(map[ny][nx]), map[ny][nx]); // 그 상어를 이동 시킨다.
}
// 다시 확인했을 때 다른 상어가 오지 않았다면
if(map[ny][nx] == 0) {
map[ny][nx] = idx;
return;
}
// 만약 도착했는데 현재 상어가 이미 위치한 상어보다 크면
if(shark.get(map[ny][nx])[5] < z) {
shark.get(map[ny][nx])[0] = -1; // 작은 상어는 죽인다
}
// 자신이 더 작으면, 자신이 죽는다
else if(shark.get(map[ny][nx])[5] > z){
shark.get(idx)[0] = -1;
return;
}
}
map[ny][nx] = idx;
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= m)
return false;
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
진행 방향을 반대로 바꾸는 revesed 배열
이동거리를 단축시키는 % 연산을 배울 수 있는 문제였다.
개선할 점
없습니다.
