[백준 17143] 낚시왕(Java)

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

이 문제는 완전탐색 문제입니다. 문제의 조건을 하나하나 구현해나가면 쉽게 풀 수 있습니다.

이 문제의 가장 핵심은 상어의 이동 방향과 이동 속도를 어떤 식으로 처리할 것인지입니다. 만약 상어의 속도를 변환 없이 진행한다면 시간 초과가 발생하기 때문입니다. 따라서 이 문제는 상어의 속도의 규칙성을 찾아야 합니다.

문제의 예시에서 가로 6칸 세로 4칸의 격자판이 있을 때, 어느 정도 이동해야 현재 위치에 현재 방향 그대로 위치하는지를 찾아야 합니다. 직접 세보면 가로 방향 10번 이동했을 때, 세로 방향 6번 이동했을 때 현재 위치에 현재 방향 그대로 존재하는 것을 알 수 있습니다.

이를 조금 더 풀어보자면 격자의 양 끝은 1번만 지나가고 나머지 부분은 2번씩 지나가므로 가로와 세로 각각

(C-1)*2, (R-1)*2

가 됨을 알 수 있습니다. 여기서 하나 더 유의할 점은, C가 가로 방향, R이 세로 방향이라는 것입니다. 이 부분에 유의해서 문제를 풀어주시면 됩니다.

그렇다면 위에서 구한 식을 어떻게 적용시키면 될까요? 우선 현재 방향에 맞게 현재 속도를 해당하는 값으로 나눈 나머지를 얻습니다. 위의 수치만큼 규칙적으로 반복한다는 뜻이기 때문에 결국 나눔으로서 불필요하게 반복되는 움직임을 크게 줄일 수 있습니다.

이렇게 나눈 수치를 하나씩 이동시키면서 가장 끝 점에 도달했을 경우 방향을 바꿔주시면 됩니다.

다음은 코드입니다.

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

public class Main{

    static int X,Y,M;
    static Shark[][] req = new Shark[101][101];
    static int res = 0;

    static void moveSharks(){
        // 큐에 현재 살아있는 상어들을 모두 넣기
        Queue<Shark> sharks = new LinkedList<>();
        for(int x=1;x<=X;x++) {
            for (int y = 1; y <= Y; y++) {
                if(req[y][x] != null) sharks.add(req[y][x]);
            }
        }

        // 전체 상어 데이터 초기화
        req = new Shark[Y+1][X+1];

        // 큐가 빌 때까지 모든 상어들 움직이기
        while(!sharks.isEmpty()){
            Shark shark = sharks.poll();

            // 상하로 움직일 경우 같은 방향을 바라보며 같은 위치에 존재할 규칙성을 나눠줌
            int speed = shark.s;
            if(shark.d == 1 || shark.d == 2) speed %= (Y-1)*2;
            else speed %= (X-1)*2;

            // 속도가 0이 될때까지 1칸씩 차례대로 움직임
            while(speed-- > 0){
                // 방향에 맞게 이동값 조정
                switch (shark.d){
                    // 위
                    case 1:
                        if(shark.y==1){
                            shark.d=2;
                            shark.y++;
                        }
                        else shark.y--;
                        break;
                    // 아래
                    case 2:
                        if(shark.y==Y){
                            shark.d=1;
                            shark.y--;
                        }
                        else shark.y++;
                        break;
                    // 오른쪽
                    case 3:
                        if(shark.x==X){
                            shark.d=4;
                            shark.x--;
                        }
                        else shark.x++;
                        break;
                    // 왼쪽
                    case 4:
                        if(shark.x==1){
                            shark.d=3;
                            shark.x++;
                        }
                        else shark.x--;
                        break;
                }
            }

            // 만약 움직일 위치에 상어가 자기보다 크다면 먹힘
            // 그 외의 경우는 해당 위치로 이동

            // 움직일 위치에 상어가 존재한다면
            if(req[shark.y][shark.x] != null){
                // 움직일 위치의 상어가 더 작다면 그 위치 그대로 들어가기
                if(req[shark.y][shark.x].size < shark.size) req[shark.y][shark.x] = shark;
            }
            // 상어가 존재하지 않는다면 그 위치로 그대로 이동
            else req[shark.y][shark.x] = shark;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            req[y][x] = new Shark(x,y,s,d,z);
        }

        // 1. 오른쪽으로 한 칸 씩 이동
        for(int x=1;x<=X;x++){
            for(int y=1;y<=Y;y++){

                // 2. 땅과 가장 가까운 상어를 잡는다.
                if(req[y][x] != null){
                    res += req[y][x].size;
                    req[y][x] = null;
                    break;
                }
            }

            // 3. 상어가 이동한다.
            moveSharks();
        }

        System.out.println(res);
    }
}

class Shark{
    int x;
    int y;
    int s;
    int d;
    int size;

    public Shark(int x, int y, int s, int d, int size){
        this.x = x;
        this.y = y;
        this.s = s;
        this.d = d;
        this.size = size;
    }
}