[backjoon] 17143 낚시왕 java

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

이 문제를 확인하면 크게 2가지를 구현해야함을 알 수 있다.

낚시와 상어의 이동

1. 낚시 : 낚시의 경우에 한 칸씩 왼쪽으로 이동하면서 0과 가까운 위치에 있는 물고기를 지워주면 된다.

2. 상어의 이동

상어가 정해진 규칙에 맞게 이동하면 된다.

한 칸에 여러 마리가 도착할 수 있는데, 한 칸엔 한 마리의 상어만 있을 수 있으며 크기가 제일 큰 상어만 남아있는다.

 

격자판이 크지 않아서 상어를 별도의 List로 관리하지 않고 계속해서 전체 파악해줬다.

풀이 

격자판의 자료 구조를 상어로 잡았다. 격자판에서 상어를 잡고 상어가 이동하기 때문이다.

상어 구조체는 상어의 크기, 방향, 스피드로 구성하였다.

낚시의 경우 일단 칸별로 이동하면서 진행하였다.

상어의 이동의 경우 일단 row와 col이 작은 순서대로 이동시켰다.

상어가 있으면 탐색을 진행하였는데, 상어 스피드에 맞게 계속해서 값을 더해주며 이동시켰다.

벽에 부딪혔다면 반대편으로 이동하였고, 방향은 별도의 메서드를 이용하였다. 제자리에 있는 것이 아니다!

최종 이동 장소에 상어가 있고, 그 상어의 사이즈가 현재 이동중인 상어보다 크다면 거기서 탐색을 종료한다.(잡아먹힘)

반대로 최종 이동 장소에 상어가 현재 이동중인 상어보다 작다면 현재 이동 중인 상어가 그 위치를 차지하게 된다.

주의해야할 것은!! 동시에 이동되기 때문에 애매하게 값이 중첩될 수 있다는 점이다.

두 상어의 위치가 A(1,3), B(3,3)이고 이동 후 A(3, 3), B(3, 1)이라고 하고 A 먼저 이동한다고 하면

하나의 맵을 사용했을 경우, A가 이동 전인 B와 겹친다고 풀이 될 수 있다. 하지만 B와 A는 만나지 않기 때문에 아예 상어를 따로 관리해주거나, 맵을 분리해주거나 해야한다. (만약 맵이 너무 크다면 상어를 별도의 자료구조를 사용해서 해야할 수도 있다.)

 

이런 방식으로 코딩하면 문제 풀이 끝!

문제 풀이시 주의 사항 및 팁은

빠른 속도를 위해 스피드를 나머지 연산자로 간결하게 하는 것이고,(엄청나게 빨라진다.)

상어의 초기 위치나 방향이 1부터 시작하기 때문에 주의해줘야한다. -> 벽에 부딪히는 부분에서 헷갈릴 수 있음.

 

 

import java.io.*;
import java.util.*;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        // << 초기화 과정 >>
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
        Shark[][] map = 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()) - 1;
            int z = Integer.parseInt(st.nextToken());
            if (d <= 1) s %= (2 * R - 2);
            else s %= (2 * C - 2);
            Shark cur = new Shark(s, d, z);
            map[r][c] = cur;
        }
 
        // << 낚시하기 >>
        int answer = 0;
        // 낚시 왕이 제일 오른쪽으로 가면 종료.
        for (int fisher = 0; fisher < C; fisher++) {
            // 상어 잡기
            for (int i = 0; i < R; i++) {
                if (map[i][fisher] != null) {
                    answer += map[i][fisher].size;
                    map[i][fisher] = null;
                    break;
                }
            }
            
            // 상어 이동하기.
            Shark[][] temp = new Shark[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (map[i][j] == null)
                        continue;
                    Shark shark = map[i][j];
                    int nextR = i;
                    int nextC = j;
                    for (int k = 0; k < shark.speed; k++) {
                        nextR += dirs[shark.dir][0];
                        nextC += dirs[shark.dir][1];
                        if (nextR < 0 || nextC < 0 || nextR >= R || nextC >= C) {
                            shark.dir = backDir(shark.dir);
                            nextR += dirs[shark.dir][0] * 2;
                            nextC += dirs[shark.dir][1] * 2;
                        }
                    }
                    if (temp[nextR][nextC] != null && temp[nextR][nextC].size > shark.size) {
                        continue;
                    }
                    temp[nextR][nextC] = shark;
                }
            }
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    map[i][j] = temp[i][j];
                }
            }
        }
        System.out.println(answer);
    }
 
    public static int backDir(int dir) {
        if (dir == 0)
            return 1;
        if (dir == 1)
            return 0;
        if (dir == 2)
            return 3;
        return 2;
    }
 
    public static class Shark {
        int speed;
        int size;
        int dir;
 
        Shark(int speed, int dir, int size) {
            this.size = size;
            this.dir = dir;
            this.speed = speed;
        }
    }
}
 

 

 

계속 못 풀다가 오랜만에 풀었을 때 금방 풀렸다...