[백준 Gold 2] 17143 낚시왕 - Java

문제링크 : https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

접근 과정 : 

• 우선 1,1 부터 시작하는 좌표를 바꾸지 그대로 사용하려고 했다. 
• 매번 낚시와 상어이동 이후에 좌표를 모두 바꿔주는 상황을 만들지 않기위해, 3차원 배열을 사용했다..
• 상어가 같은 방향을 가지고 원래 자리로 돌아오는 것은 s = (범위-1)x2 인 것을 고려하여 s % (범위-1)x2를 적용.
• 그리고 상어 이동을 점화식으로 만들려고 했는데... 생각나지 않아서.. s만큼 하나씩 이동했다..ㅜ 

 

소스 코드 및 결과 :

package BOJ;

/* 
    낚시왕
*/

import java.io.*;
import java.util.*;

public class BOJ17143 {

    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());

        map = new int[R + 1][C + 1][C + 1];

        Queue<Shark> queue = new LinkedList<>();
        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 s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            if (d <=2) {
                s %= ((R-1)*2);
            }else{
                s %= ((C-1)*2);
            }

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

            map[r][c][1] = z;

        }

        int sum = 0;

        // 낚시꾼 이동
        for (int x = 1; x <= C; x++) {

            // 낚시
            for (int i = 1; i <= R; i++) {
                if (map[i][x][x] != 0) {
                    sum += map[i][x][x];
                    map[i][x][x] = 0;
                    break;
                }
            }

            // 상어 이동

            if (x == C) {
                break;
            }

            int size = queue.size();
            while (size-- > 0) {

                Shark shark = queue.poll();

                if (map[shark.r][shark.c][x] != shark.z) {
                    continue;
                }

                shark = move(shark);

                map[shark.r][shark.c][x + 1] = Math.max(map[shark.r][shark.c][x + 1], shark.z);
                queue.add(shark);

            }

        }

        System.out.println(sum);

    }

    static int R, C, M;
    static int[][][] map;
    static int[][] dir = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };

    private static class 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;
        }
    }

    static Shark move(Shark shark) {

        // 상하 이동
        if (shark.d <= 2) {

            for (int i = 0; i < shark.s; i++) {
                shark.r += dir[shark.d][0];

                if (shark.r == 0 && shark.d == 1) {
                    shark.r = 2;
                    shark.d = 2;
                } else if (shark.r == R + 1 && shark.d == 2) {
                    shark.r = R - 1;
                    shark.d = 1;
                }

            }

        } else { // 좌우 이동
            for (int i = 0; i < shark.s; i++) {
                shark.c += dir[shark.d][1];
                if (shark.c == 0 && shark.d == 4) {
                    shark.c = 2;
                    shark.d = 3;
                } else if (shark.c == C + 1 && shark.d == 3) {
                    shark.c = C - 1;
                    shark.d = 4;
                }

            }
        }

        return shark;
    }
}

 

P.S 

왜.. 상어 이동의 점화식이 떠오르지 않을까...

최대한 좌표는 바꾸지 않고 하고 싶은데.. 

그 부분만 처리하면 시간은 상당히 줄어들 듯