[백준 Baekjoon] 17143번 낚시왕 - JAVA

[백준 Baekjoon] 17143번 낚시왕 - JAVA

---

문제 풀이

Shark[][] grid : 상어가 격자에 두 마리 존재하는지와 땅에서 가장 가까운 상어를 찾는 데 사용합니다.

List<Shark> list : 격자에 존재하는 상어를 관리하는 데 사용합니다.

 

낚시왕이 오른쪽으로 한 칸 이동하며 상어를 잡는 행동과, 상어 이동을 호출합니다.

// 낚시왕이 오른쪽으로 한 칸 이동
for (int i = 0; i < C; i++) {
    fishing(i);

    move();
}

 

낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡습니다.

잡은 상어는 격자와 리스트에서 모두 제거해줍니다.

for (int r = 0; r < R; r++) {
    // 까가장 가까운 상어를 잡는다.
    if (grid[r][c] != null) {
        // 잡은 상어 크기의 합을 갱신
        answer += grid[r][c].z;

        // 상어를 잡으면 상어가 사라진다.
        list.remove(grid[r][c]);
        grid[r][c] = null;

        break;
    }
}

 

상어의 이동을 수행합니다.

상어는 입력으로 주어진 속도로 이동합니다. 이동하려고 하는 칸이 격자판의 경계를 넘는 경우 방향을 반대로 바꿔 속력을 유지한 채로 이동합니다. 공식을 세워 한번에 계산하려 했으나 잘 안되어서 속도만큼 반복하며 이동하는 방식으로 처리하였습니다.

 

입력으로 주어진 속도로 이동하는 것은 행으로 이동할 때는 (R - 1) * 2로, 열로 이동할 때는 (C - 1) * 2로 나머지 연산한 값과 동일한 결과가 나옵니다.

int s = (shark.d == 0 || shark.d == 2) ? shark.s % ((R - 1) * 2) : shark.s % ((C - 1) * 2);

 

속도만큼 이동하며 격자판의 경계를 넘는 경우 왔던 방향의 반대로 2번 이동합니다.

// 속도만큼 이동
for (int j = 0; j < s; j++) {
    shark.r += dx[shark.d];
    shark.c += dy[shark.d];

    // 격자를 벗어나는 경우 반대방향으로 이동
    if (shark.r < 0 || shark.c < 0 || shark.r >= R || shark.c >= C) {
        shark.r -= dx[shark.d] * 2;
        shark.c -= dy[shark.d] * 2;

        // 방향 변경
        shark.d = (shark.d + 2) % 4;
    }
}

방향을 (현재 방향 + 2) % 4로 반대 방향으로 변경합니다.

이것을 편하게 하기 위해 방향을 상, 좌, 하, 우 순으로 저장하였습니다.

public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, -1, 0, 1};

if (d == 1) { // 방향을 상, 좌, 하, 우로 저장
    d = 0;
} else if (d == 4) {
    d = 1;
}

 

상어가 두마리 이상인 경우 격자에 존재하는 상어와 현재 상어를 비교하여 작은 상어를 격자에 저장하고 리스트에서 제거합니다.

격자에 상어가 없는 경우는 현재 상어를 격자에 저장해줍니다.

if (grid[shark.r][shark.c] != null) { // 상어가 두 마리 이상 있는 경우
    if (grid[shark.r][shark.c].z > shark.z) { // 격자의 상어가 큰 경우
        list.remove(shark); // 현재 상어를 제거
    } else { // 현재 상어가 큰 경우
        list.remove(grid[shark.r][shark.c]); // 격자의 상어를 제거
        grid[shark.r][shark.c] = shark; // 현재 상어를 격자에 저장
    }
} else { // 격자에 상어가 없는 경우
    grid[shark.r][shark.c] = shark;
}

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int R, C;
    public static int answer;

    public static Shark[][] grid;
    public static List<Shark> list = new ArrayList<>();

    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {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());
        C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        grid = new Shark[R][C];

        for (int i = 0; i < M; i++) {
            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());

            if (d == 1) { // 방향을 상, 좌, 하, 우로 저장
                d = 0;
            } else if (d == 4) {
                d = 1;
            }

            list.add(new Shark(r, c, s, d, z));

            grid[r][c] = list.get(i);
        }

        // 낚시왕이 오른쪽으로 한 칸 이동
        for (int i = 0; i < C; i++) {
            fishing(i);

            move();
        }

        System.out.println(answer);
    }

    public static void move() {
        grid = new Shark[R][C];
        int size = list.size();

        for (int i = size - 1; i >= 0; i--) {
            Shark shark = list.get(i);

            // 속도가 이동 행, 열 -1의 2배이면 나머지 연산한 값과 동일
            int s = (shark.d == 0 || shark.d == 2) ? shark.s % ((R - 1) * 2) : shark.s % ((C - 1) * 2);

            // 속도만큼 이동
            for (int j = 0; j < s; j++) {
                shark.r += dx[shark.d];
                shark.c += dy[shark.d];

                // 격자를 벗어나는 경우 반대방향으로 이동
                if (shark.r < 0 || shark.c < 0 || shark.r >= R || shark.c >= C) {
                    shark.r -= dx[shark.d] * 2;
                    shark.c -= dy[shark.d] * 2;

                    // 방향 변경
                    shark.d = (shark.d + 2) % 4;
                }
            }

            if (grid[shark.r][shark.c] != null) { // 상어가 두 마리 이상 있는 경우
                if (grid[shark.r][shark.c].z > shark.z) { // 격자의 상어가 큰 경우
                    list.remove(shark); // 현재 상어를 제거
                } else { // 현재 상어가 큰 경우
                    list.remove(grid[shark.r][shark.c]); // 격자의 상어를 제거
                    grid[shark.r][shark.c] = shark; // 현재 상어를 격자에 저장
                }
            } else { // 격자에 상어가 없는 경우
                grid[shark.r][shark.c] = shark;
            }
        }
    }

    public static void fishing(int c) {
        for (int r = 0; r < R; r++) {
            // 까가장 가까운 상어를 잡는다.
            if (grid[r][c] != null) {
                // 잡은 상어 크기의 합을 갱신
                answer += grid[r][c].z;

                // 상어를 잡으면 상어가 사라진다.
                list.remove(grid[r][c]);
                grid[r][c] = null;

                break;
            }
        }
    }

    public static class Shark {
        int r, c, s, d, 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;
        }
    }

}